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 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 increase 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 .
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.