# 2013 IMO Problems/Problem 1

## Problem

Prove that for any pair of positive integers and , there exist positive integers (not necessarily different) such that

.

## Solution

We prove the claim by induction on .

**Base case:** If then , so the claim is true for all positive integers .

**Inductive hypothesis:** Suppose that for some the claim is true for , for all .

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

[Case 1: is even]

[Case 2: is odd]

In either case, for some .

By the induction hypothesis we can choose such that .

Therefore, since was arbitrary, the claim is true for , for all . Our induction is complete and the claim is true for all positive integers , .

## Alternative Solution

We will prove the claim by constructing telescoping product out of positive integers: where and where each fraction can also be written as for some positive integer . All will be different with , . .

**Ascend:** make telescoping product of fractions with a sequence of that increases in magnitude up to the maximum . If the maximum is reached go to the descend phase.
Pull out factors of (up to the maximum ).
, etc where , ...
Construct telescoping as . The corresponding differences are ... Every is bigger then the previous by at least factor . Therefore, the biggest needed can be created telescoping at most fractions. After we constructed the fraction with the biggest needed we can construct any remaining needed as described below.

**Descend:**
If we need where we can use as the next telescoping fraction . We can construct all the remaining nedded in the decreasing order of their magnitude by repeating the same step.

--alexander_skabelin 9:24, 11 July 2023 (EST)

*Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.*