Difference between revisions of "2013 IMO Problems/Problem 1"
Skywalker94 (talk | contribs) m (→Solution: Fixed inconsistent formatting.) |
(→See Also) |
||
(12 intermediate revisions by one other user not shown) | |||
Line 22: | Line 22: | ||
Therefore, since <math>n</math> was arbitrary, the claim is true for <math>k = m+1</math>, for all <math>n</math>. Our induction is complete and the claim is true for all positive integers <math>n</math>, <math>k</math>. | Therefore, since <math>n</math> was arbitrary, the claim is true for <math>k = m+1</math>, for all <math>n</math>. Our induction is complete and the claim is true for all positive integers <math>n</math>, <math>k</math>. | ||
+ | |||
+ | ==Alternative Solution== | ||
+ | We will prove the claim by constructing telescoping product out of positive integers: | ||
+ | <cmath>\frac{a_2}{a_1}\cdot\frac{a_3}{a_2}\cdot\frac{a_4}{a_3}\cdot \cdot \frac{a_{k+1}}{a_k} = \frac{a_{k+1}}{a_1} = \frac{\left(n+2^{k}-1\right)}{n}</cmath> | ||
+ | where <math>a_1=n</math> and where each fraction <math>\frac{a_{i+1}}{a_i}=\frac{a_{i}+\Delta_i}{a_i}</math> can also be written as <math>\frac{m_i+1}{m_i}</math> for some positive integer <math>m_i</math>. All <math>\Delta_i</math> will be different with <math>\Delta_i=2^j</math>, <math>0\le j \le (k-1)</math>. <math>\sum_{i=1}^{k}{\Delta_i}=\sum_{i=1}^{k}{2^{i-1}}=2^{k}-1</math>. | ||
+ | |||
+ | '''Ascend:''' make telescoping product of fractions with a sequence of <math>\Delta_i</math> that increases in magnitude up to the maximum <math>2^{k-1}</math>. If the maximum <math>\Delta=2^{k-1}</math> is reached go to the descend phase. | ||
+ | Pull out factors of <math>2</math> (up to the maximum <math>2^{k-1}</math>). | ||
+ | <math>n=2^j(2z+1)</math>, <math>z+1=2^q(2r+1)</math> etc where <math>j\ge 0</math>, <math>q\ge 0</math> ... | ||
+ | Construct telescoping as <cmath>\frac{2^j(2z+2)}{2^j(2z+1)}\cdot \frac{2^{j+q+1}(2r+2)}{2^{j+q+1}(2r+1)} ...</cmath>. The corresponding differences <math>\Delta</math> are <math>2^j, 2^{j+q+1}</math> ... Every <math>\Delta_i</math> is bigger then the previous <math>\Delta_{i-1}</math> by at least factor <math>2</math>. Therefore, the biggest needed <math>\Delta=2^{k-1}</math> can be created telescoping at most <math>k</math> fractions. After we constructed the fraction <math>\frac{2^{k-1}(h+1)}{2^{k-1}h}</math> with the biggest needed <math>\Delta=2^{k-1}</math> we can construct any remaining needed <math>\Delta_i</math> as described below. | ||
+ | |||
+ | '''Descend:''' | ||
+ | If we need <math>\Delta=2^{d}</math> where <math>d<k-1</math> we can use as the next telescoping fraction <math>\frac{2^{d}(2^{k-1-d}(h+1)+1)}{2^{d}(2^{k-1-d}(h+1))}</math>. We can construct all the remaining nedded <math>\Delta_i</math> in the decreasing order of their magnitude by repeating the same step. | ||
+ | |||
+ | --[[User:alexander_skabelin|alexander_skabelin]] 9:24, 11 July 2023 (EST) | ||
+ | |||
+ | {{alternate solutions}} | ||
==See Also== | ==See Also== | ||
*[[2013 IMO]] | *[[2013 IMO]] | ||
+ | {{IMO box|year=2013|before=First Problem|num-a=2}} |
Latest revision as of 00:30, 19 November 2023
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.
See Also
2013 IMO (Problems) • Resources | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |