IMO 2013 · Problem 1

Prove that for any pair of positive integers \(k\) and \(n\), there exist \(k\) positive integers \(m_1,m_2,\ldots,m_k\) (not necessarily different) such that \[ 1+\frac{2^k-1}{n} = \left(1+\frac{1}{m_1}\right) \left(1+\frac{1}{m_2}\right) \cdots \left(1+\frac{1}{m_k}\right). \]

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

Solution

We use induction on \(k\), proving the assertion for every positive integer \(n\) simultaneously.

For \(k=1\), take \(m_1=n\).

Now let \(k\ge 2\) and assume the assertion holds for \(k-1\) and every positive integer denominator. Fix a positive integer \(n\).

If \(n\) is odd, then \(r=(n+1)/2\) is a positive integer. By the induction hypothesis, there exist positive integers \(m_1,\ldots,m_{k-1}\) such that \[ \prod_{i=1}^{k-1}\left(1+\frac1{m_i}\right) =1+\frac{2^{k-1}-1}{r} =\frac{n+2^k-1}{n+1}. \] Taking \(m_k=n\), we obtain \[ \prod_{i=1}^{k}\left(1+\frac1{m_i}\right) = \frac{n+2^k-1}{n+1}\cdot\frac{n+1}{n} = 1+\frac{2^k-1}{n}. \]

If \(n\) is even, then \(r=n/2\) is a positive integer. By the induction hypothesis, there exist positive integers \(m_1,\ldots,m_{k-1}\) such that \[ \prod_{i=1}^{k-1}\left(1+\frac1{m_i}\right) =1+\frac{2^{k-1}-1}{r} =\frac{n+2^k-2}{n}. \] Taking the positive integer \(m_k=n+2^k-2\), we obtain \[ \prod_{i=1}^{k}\left(1+\frac1{m_i}\right) = \frac{n+2^k-2}{n}\cdot \frac{n+2^k-1}{n+2^k-2} = 1+\frac{2^k-1}{n}. \]

Both cases establish the induction step, so the assertion holds for all positive integers \(k\) and \(n\). \(\square\)

The solution was checked against the official IMO shortlist solutions.