IMO 2012 · Problem 6

Find all positive integers \(n\) for which there exist non-negative integers \(a_1,a_2,\ldots,a_n\) such that \[ \frac{1}{2^{a_1}}+\frac{1}{2^{a_2}}+\cdots+\frac{1}{2^{a_n}} = \frac{1}{3^{a_1}}+\frac{2}{3^{a_2}}+\cdots+\frac{n}{3^{a_n}} =1. \]

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

Answer

Exactly the positive integers \[ \boxed{n\equiv 1\ \text{or}\ 2\pmod 4}. \]

Solution

Suppose such integers exist, and let \(M=\max(a_1,\ldots,a_n)\). Multiplying the second equality by \(3^M\) gives \[ \sum_{i=1}^n i\,3^{M-a_i}=3^M. \] Reducing modulo \(2\), we obtain \[ \frac{n(n+1)}2=\sum_{i=1}^n i\equiv1\pmod2. \] Thus \(n\equiv1\) or \(2\pmod4\).

We now construct solutions for all these integers. The following starting cases are verified by the sums shown:

\(n\) \((a_1,\ldots,a_n)\) \(\sum 2^{-a_i}\) \(\sum i3^{-a_i}\)
\(1\) \((0)\) \(1\) \(1\)
\(2\) \((1,1)\) \(2/2=1\) \(3/3=1\)
\(5\) \((2,2,2,3,3)\) \(3/4+2/8=1\) \(6/9+9/27=1\)
\(6\) \((2,2,3,3,3,3)\) \(2/4+4/8=1\) \(3/9+18/27=1\)
\(9\) \((2,2,4,4,4,3,4,4,4)\) \(2/4+1/8+6/16=1\) \(3/9+6/27+36/81=1\)

Both the \(n=6\) and \(n=9\) solutions have the additional property \[ a_3=a_{n-1}. \] We show that any solution with \(n\ge6\) having this property produces a solution for \(n+4\) with the same property.

Write \(t=a_3=a_{n-1}\). Define \(b_1,\ldots,b_{n+4}\) by keeping \(b_i=a_i\) for all old indices except \(3\) and \(n-1\), and setting \[ b_3=b_{n-1}=b_{n+3}=b_{n+4}=t+2, \qquad b_{n+1}=b_{n+2}=t+1. \] All these exponents are non-negative integers.

In the binary sum, the two changed old terms had total \(2/2^t\). Their replacements, including the four new terms, have total \[ \frac{4}{2^{t+2}}+\frac{2}{2^{t+1}} =\frac{2}{2^t}. \] Consequently, the binary sum remains \(1\).

In the ternary sum, the two changed old terms had total \[ \frac{3+(n-1)}{3^t}=\frac{n+2}{3^t}. \] Their replacements have total \[ \begin{aligned} &\frac{3+(n-1)+(n+3)+(n+4)}{3^{t+2}} +\frac{(n+1)+(n+2)}{3^{t+1}}\\ &\qquad=\frac{3n+9+3(2n+3)}{3^{t+2}} =\frac{9(n+2)}{3^{t+2}} =\frac{n+2}{3^t}. \end{aligned} \] Thus the ternary sum also remains \(1\). Moreover, \[ b_3=b_{(n+4)-1}=t+2, \] so the additional property is preserved and the construction can be repeated.

Starting from \(n=6\) gives every \(n=6+4k\), and starting from \(n=9\) gives every \(n=9+4k\), for \(k\ge0\). Together with \(n=1,2,5\), these are precisely all positive integers congruent to \(1\) or \(2\) modulo \(4\).

The solution was checked against the official IMO shortlist solutions.