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 construct 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 , . .
Let's pull out factors of if there are any: , etc where , . Construct telescoping as . Every can be bigger then previous by at least factor . The biggest needed can be constructed in at most steps. After we constructed the fraction with the biggest needed : we can construct any remaining needed in the decresing order. That is if we need where we can use as the next telescoping fraction
--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.