IMO 2019 · Problem 4

Find all pairs \((k,n)\) of positive integers such that \[ k! = (2^n - 1)(2^n - 2)(2^n - 4)\cdots(2^n - 2^{n-1}). \]

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{(k,n)=(1,1)\ \text{or}\ (3,2).} \]

Solution

Let \(v_2(a)\) denote the exponent of \(2\) in the prime factorization of a positive integer \(a\). Since \[ \prod_{j=0}^{n-1}(2^n-2^j) = 2^{n(n-1)/2}\prod_{j=1}^{n}(2^j-1), \] and every factor \(2^j-1\) is odd, the given equation implies \[ v_2(k!)=\frac{n(n-1)}2. \] Counting multiples of \(2,4,8,\ldots\) among \(1,\ldots,k\), we obtain \[ v_2(k!)=\sum_{r\ge1}\left\lfloor\frac{k}{2^r}\right\rfloor <\sum_{r\ge1}\frac{k}{2^r}=k. \] Consequently, \[ k\ge m_n,\qquad m_n:=\frac{n(n-1)}2+1. \] Meanwhile, each of the \(n\) factors on the right-hand side of the original equation is less than \(2^n\), so \[ k!<2^{n^2}. \]

We now prove that \[ m_n!>2^{n^2}\qquad\text{for every }n\ge5. \] For \(n=5\), this follows from \[ m_5!=11!=39\,916\,800>33\,554\,432=2^{25}. \] Suppose the inequality holds for some \(n\ge5\). Since \(m_{n+1}=m_n+n\) and \(m_n\ge11\), we have \[ m_{n+1}! =m_n!\prod_{t=1}^{n}(m_n+t) >2^{n^2}\,8^n =2^{n^2+3n} >2^{(n+1)^2}, \] where the last inequality uses \(n>1\). This completes the induction.

Thus \(n\ge5\) is impossible: it would give \[ k!\ge m_n!>2^{n^2}, \] contrary to \(k!<2^{n^2}\).

It remains to check \(n=1,2,3,4\):

  • If \(n=1\), the equation is \(k!=1\), giving \(k=1\).
  • If \(n=2\), the equation is \(k!=3\cdot2=6\), giving \(k=3\).
  • If \(n=3\), the right-hand side is \(7\cdot6\cdot4=168\), and \[ 5!=120<168<720=6!, \] so there is no solution.
  • If \(n=4\), the right-hand side is \(15\cdot14\cdot12\cdot8=20\,160\), and \[ 7!=5\,040<20\,160<40\,320=8!, \] so there is no solution.

Both stated pairs satisfy the equation, completing the proof.

The solution was checked against the official IMO shortlist solutions.