Difference between revisions of "1978 USAMO Problems/Problem 3"
m |
(→Solution) |
||
(5 intermediate revisions by 2 users not shown) | |||
Line 9: | Line 9: | ||
Given the information that the integers 33 through 73 are good, prove that every integer <math>\ge 33</math> is good. | Given the information that the integers 33 through 73 are good, prove that every integer <math>\ge 33</math> is good. | ||
+ | |||
+ | ==Hint== | ||
+ | Is there an algorithm to deduce another good integer given a good integer? You might want to use the fact that <math>1 = \frac{1}{2} + \frac{1}{2}</math>. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
== Solution == | == Solution == | ||
− | {{ | + | ''Lemma:'' If <math>g</math> is a good integer, then so is <math>2g + 2</math> and <math>2g + 9</math>. |
+ | |||
+ | Proof: Let <math>g = a_1 + a_2 + \cdots + a_k</math> such that <cmath>\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_k}=1,</cmath> where the <math>a_i</math> are positive integers. Then, notice that <cmath>1 = \frac{1}{2} + \frac{1}{2} = \frac{1}{2} + \frac{1}{2a_1}+\frac{1}{2a_2}+\cdots+\frac{1}{2a_k},</cmath> so <math>g_1 = 2 + 2a_1 + 2a_2 + ... + 2a_k = 2 + 2g</math> is also a good integer. Furthermore, <cmath>1 = \frac{1}{3} + \frac{1}{6} + \frac{1}{2} = \frac{1}{3} + \frac{1}{6} + \frac{1}{2a_1}+\frac{1}{2a_2}+\cdots+\frac{1}{2a_k},</cmath> so <math>g_2 = 3 + 6 + 2a_1 + 2a_2 + ... + a_k = 9 + 2g</math> is also good. | ||
+ | |||
+ | This completes the lemma. Now, we use induction to show that the integers from 33 to <math>n</math> are all good, where <math>n \ge 33</math>. | ||
+ | |||
+ | Base case: Our given takes care of <math>33 \le n \le 73</math>. | ||
+ | Inductive step: Assume the integers between 33 and <math>k > 73</math>, inclusive, are all good. Now, we casework on parity of <math>k+1</math>. | ||
+ | |||
+ | If <math>k+1</math> is odd, then write <math>k+1 = 2g + 9</math> for some integer <math>g</math>. | ||
+ | |||
+ | It follows that because <math>k \ge 74</math>, we must have | ||
+ | |||
+ | <cmath>g = \frac{k}{2} - 4 \ge 37 - 4 = 33.</cmath> | ||
+ | |||
+ | Thus, <math>33 \le g < \frac{k}{2}</math>, and so <math>g</math> is good by the inductive hypothesis. Applying the lemma gives <math>2g + 9 = k+1</math> as a good integer. | ||
+ | |||
+ | If <math>k+1</math> is even, write <math>k+1 = 2g+2</math> for some integer <math>g</math>. Therefore, <cmath>g = \frac{k-1}{2} > \frac{73-1}{2} = 36 > 33,</cmath> so that <math>33 < g < \frac{k}{2}</math>, meaning that <math>g</math> is a good integer by the inductive hypothesis. From the lemma, <math>k+1</math> must be good as well. | ||
+ | |||
+ | This completes the inductive step and thus the induction. Therefore, all integers <math>n \ge 33</math> are good integers. | ||
== See Also == | == See Also == | ||
{{USAMO box|year=1978|num-b=2|num-a=4}} | {{USAMO box|year=1978|num-b=2|num-a=4}} | ||
+ | {{MAA Notice}} | ||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] |
Latest revision as of 17:52, 14 August 2014
Contents
Problem
An integer will be called good if we can write
,
where are positive integers (not necessarily distinct) satisfying
.
Given the information that the integers 33 through 73 are good, prove that every integer is good.
Hint
Is there an algorithm to deduce another good integer given a good integer? You might want to use the fact that .
Solution
Lemma: If is a good integer, then so is
and
.
Proof: Let such that
where the
are positive integers. Then, notice that
so
is also a good integer. Furthermore,
so
is also good.
This completes the lemma. Now, we use induction to show that the integers from 33 to are all good, where
.
Base case: Our given takes care of .
Inductive step: Assume the integers between 33 and
, inclusive, are all good. Now, we casework on parity of
.
If is odd, then write
for some integer
.
It follows that because , we must have
Thus, , and so
is good by the inductive hypothesis. Applying the lemma gives
as a good integer.
If is even, write
for some integer
. Therefore,
so that
, meaning that
is a good integer by the inductive hypothesis. From the lemma,
must be good as well.
This completes the inductive step and thus the induction. Therefore, all integers are good integers.
See Also
1978 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.