2019 IMO Problems/Problem 4

Revision as of 02:29, 9 February 2020 by Phoenixfire (talk | contribs) (Solution 1)

Problem

Find all pairs $(k,n)$ of positive integers such that

\[k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1}).\]

Solution 1

$LHS$

$k! = 1$ (when $k = 1$), $2$ (when $k = 2$), $6$ (when $k = 3$)

$RHS = 1$(when $n = 1$), $6$ (when $n = 2$)

Hence, $(1,1)$, $(3,2)$ satisfy

For $k = 2: RHS$ is strictly increasing, and will never satisfy $k$ = 2 for integer n since $RHS = 6$ when $n = 2$.

\[k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})  ...                                                                       (1)\]

In all solutions, for any prime $p$ and positive integer $N$, we will denote by \[v_p(N)\] the exponent of the largest power of $p$ that divides $N$. The right-hand side of $(1)$ will be denoted by \[L_n;\] that is, \[L_n = (2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})\]

\[(2^{1+2+3+\dots+(n-1)})(2^n-1)(2^{n-1}-1)(2^{n-2}-1)\dots(2^1-1)\] = \[v_2(L_n) = (2^{\frac{n(n-1)}{2}})\]

On the other hand, \[v_2(k!)\] is expressed by the $Legendre$ $formula$ as \[v_2(k!) < \sum_{i=1}^{\infty} (\frac{k}{2^i})) = k\]

Thus, $k! = L_n$ implies the inequality \[\frac{n(n-1)}{2} < k    ...                                                   (2)\] In order to obtain an opposite estimate, observe that \[L_n = (2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})\] We claim that \[2^{n^2} < (\frac{n(n-1)}{2})!                   ...                                                     (3)\] for all $n \geq 6$

For $n \geq 6$ the estimate (3) is true because \[2^{6^2} < (6.9)(10^{10})\] and \[(\frac{n(n-1)}{2})! = 15! > (1.3)(10^{12})\] ~flamewavelight and phoenixfire