2013 IMO Problems/Problem 1

Problem

Prove that for any pair of positive integers $k$ and $n$ , there exist $k$ positive integers $m_1,m_2,...,m_k$ (not necessarily different) such that

$1+\frac{2^k-1}{n}=(1+\frac{1}{m_1})(1+\frac{1}{m_2})...(1+\frac{1}{m_k})$ .

Solution

We prove the claim by induction on $k$ .

Base case: If $k = 1$ then $1 +\frac{2^1-1}{n} = 1 + \frac{1}{n}$ , so the claim is true for all positive integers $n$ .

Inductive hypothesis: Suppose that for some $m \in \mathbb{Z}^{+}$ the claim is true for $k = m$ , for all $n \in \mathbb{Z}^{+}$ .

Inductive step: Let $n$ be arbitrary and fixed. Case on the parity of $n$ :

[Case 1: $n$ is even] $1 + \frac{2^{m+1} - 1}{n} = \left( 1 + \frac{2^{m} - 1}{\frac{n}{2}} \right) \cdot \left( 1 + \frac{1}{n + 2^{m+1} - 2} \right)$

[Case 2: $n$ is odd] $1 + \frac{2^{m+1} - 1}{n} = \left( 1 + \frac{2^{m}-1}{\frac{n+1}{2}} \right) \cdot \left( 1 + \frac{1}{n} \right)$

In either case, $1 + \frac{2^{m+1} - 1}{n} = \left( 1 + \frac{2^m - 1}{c} \right) \cdot \left( 1 + \frac{1}{a_{m+1}} \right)$ for some $c, a_{m+1} \in \mathbb{Z}^+$ .

By the induction hypothesis we can choose $a_1, ..., a_m$ such that $\left( 1 + \frac{2^m - 1}{c} \right) = \prod_{i=1}^{m} (1 + \frac{1}{a_i})$ .

Therefore, since $n$ was arbitrary, the claim is true for $k = m+1$ , for all $n$ . Our induction is complete and the claim is true for all positive integers $n$ , $k$ .

Alternative Solution

We will prove by constructing telescoping product: $\frac{a_2}{a_1}\cdot\frac{a_3}{a_2}\cdot\frac{a_4}{a_3} \cdot \frac{a_{k+1}}{a_k} = \frac{a_{k+1}}{a_1} = \frac{\left(a_1+2^{k}-1\right)}{a_1}$ where $a_1=n$ and each fraction $\frac{a_{i+1}}{a_i}=\frac{a_{i}+\Delta_i}{a_i}$ can also be written as $\frac{m_i+1}{m_i}$ for some positive integer $m_i$ . $\sum_{i=1}^{k}{\Delta_i}=2^{k}-1$ from telescoping property.

We will show that the set of all $\Delta_i$ can be taken to be a set of $2^j$ where $0\le j \le k-1$ . Fractions with $\Delta_i$ of this form can be constructed in the following way. We will start buiding telescoping product by trying to construct the highest remaining required $\Delta_j$ . If $n$ is odd use fraction $\frac{n+1}{n}$ , else you can use $\frac{\frac{n}{2}+1}{\frac{n}{2}}=\frac{n+2}{n}$ which constructs $\Delta=2$ . If ${\frac{n}{2}}$ is even we instead can use $\frac{\frac{n}{4}+1}{\frac{n}{4}}=\frac{n+2^2}{n}$ which constructs $\Delta=2^2$ etc. If finally ${\frac{n}{2^j}}$ is odd and $j<k-1$ then we use fraction $\frac{\frac{n}{2^j}+1}{\frac{n}{2^j}}=\frac{n+2^j}{n}$ that has $\Delta=2^j$ . In that case the next fraction from our telescoping series has denominator $\frac{n}{2^j}+1$ which is even so we can take $\frac{\frac{\frac{n}{2^j}+1}{2}+1}{\frac{\frac{n}{2^j}+1}{2}}=\frac{n+3\cdot 2^j}{n+2^j}$ which has $\Delta=2^{j+1}$ . That is we can use at most one step ( one fraction from the telescoping product) to increase $\Delta$ by factor of $2$ . In the worst case we will reach the highest $\Delta=2^{k-1}$ using $k$ steps ( $k$ fractions in the telescoping product). All other needed $\Delta_i=2^(i-1)$ would be already constructed by that time. In the best case $n= 2^q$ where $q \ge k-1$ and we can construct the highest needed $\Delta$ using the very 1st fraction.