Do there exist positive integers $b,n>1$ such that when $n$ is expressed in base $b$, there are more than $n$ distinct permutations of its digits? For example, when $b=4$ and $n=18$, $18 = 102_4$, but $102$ only has $6$ digit arrangements. (Leading zeros are allowed in the permutations.) Lewis Chen.
Problem
Source: ELMO Shortlist 2012, N4
Tags: factorial, number theory proposed, number theory
hyperbolictangent
06.07.2012 02:55
Suppose there existed such a pair $n, b$, and let $r$ be the number of digits in the base $b$ representation of $n$, so that $b^{r - 1} \le n < b^r$. For each of the $b$ possible digits $i$ in base $b$, let $a_i$ denote the number of $i$'s in the representation of $n$. Then the number of permutations of digits in base $b$ is given by \[\frac{(a_0 + a_1 + \dots a_{b - 1})!}{(a_0!)(a_1!)\dots(a_{b - 1}!)} = \frac{r!}{(a_0!)(a_1!)\dots(a_{b - 1}!)}\]
where \[\sum{a_i} = r\] For a fixed $r$ the number of permutations of digits is maximized when the factorial product in the denominator is minimized. If some $a_i, a_j$ satisfy $a_i - a_j \ge 2$, we can replace them with $a_i - 1$ and $a_j + 1$, respectively, and decrease the product. So no two $a_i$ may differ by more than $1$.
Let $r = pb + q$. Then the number of permutations of digits is at most \[\frac{r!}{p!^{(b - q)}(p + 1)!^q} = \] \[\Bigg( \frac{(pb + q)(pb + q - 1)\dots(pb + 1)}{(p + 1)^q} \Bigg) \Bigg(\frac{(pb)!}{(p!)^b}\Bigg) \le \] \[ (b^q)\prod_{k = 1}^{p}{\Bigg(\frac{(kb)(kb - 1)\dots((k - 1)b + 1)}{k^b} \Bigg) = }\] \[(b^q)(b!)\prod_{k = 2}^{p}{\Bigg(\frac{(kb)(kb - 1)\dots((k - 1)b + 1)}{k^b} \Bigg) \le }\] \[(b^q)(b!)(b^b)^{p - 1} \le\] \[(b^q)(b^{b - 1})(b^{b(p - 1)}) \le \] \[b^{bp + q - 1} \le n\] contradiction. Hence there exist no such $b, n$. The closest we can ever get is when the number of permutations equals $n$ - in this case take $b = n = 2$.
FinalSix
01.09.2013 17:16
Good problem,but I think it's not about number theroy.