Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1978 USAMO Problems/Problem 3"
(→‎Solution)
 
(4 intermediate revisions by the same user 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 ==
−
{{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 ==

Latest revision as of 16:52, 14 August 2014

Problem

An integer $n$ will be called good if we can write

$n=a_1+a_2+\cdots+a_k$,

where $a_1,a_2, \ldots, a_k$ are positive integers (not necessarily distinct) satisfying

$\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_k}=1$.

Given the information that the integers 33 through 73 are good, prove that every integer $\ge 33$ is good.

Hint

Is there an algorithm to deduce another good integer given a good integer? You might want to use the fact that $1 = \frac{1}{2} + \frac{1}{2}$.




Solution

Lemma: If $g$ is a good integer, then so is $2g + 2$ and $2g + 9$.

Proof: Let $g = a_1 + a_2 + \cdots + a_k$ such that \[\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_k}=1,\] where the $a_i$ are positive integers. Then, notice that \[1 = \frac{1}{2} + \frac{1}{2} = \frac{1}{2} + \frac{1}{2a_1}+\frac{1}{2a_2}+\cdots+\frac{1}{2a_k},\] so $g_1 = 2 + 2a_1 + 2a_2 + ... + 2a_k = 2 + 2g$ is also a good integer. Furthermore, \[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},\] so $g_2 = 3 + 6 + 2a_1 + 2a_2 + ... + a_k = 9 + 2g$ is also good.

This completes the lemma. Now, we use induction to show that the integers from 33 to $n$ are all good, where $n \ge 33$.

Base case: Our given takes care of $33 \le n \le 73$. Inductive step: Assume the integers between 33 and $k > 73$, inclusive, are all good. Now, we casework on parity of $k+1$.

If $k+1$ is odd, then write $k+1 = 2g + 9$ for some integer $g$.

It follows that because $k \ge 74$, we must have

\[g = \frac{k}{2} - 4 \ge 37 - 4 = 33.\]

Thus, $33 \le g < \frac{k}{2}$, and so $g$ is good by the inductive hypothesis. Applying the lemma gives $2g + 9 = k+1$ as a good integer.

If $k+1$ is even, write $k+1 = 2g+2$ for some integer $g$. Therefore, \[g = \frac{k-1}{2} > \frac{73-1}{2} = 36 > 33,\] so that $33 < g < \frac{k}{2}$, meaning that $g$ is a good integer by the inductive hypothesis. From the lemma, $k+1$ must be good as well.

This completes the inductive step and thus the induction. Therefore, all integers $n \ge 33$ 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1978_USAMO_Problems/Problem_3&oldid=63074"