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"
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}{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, 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 > 3,</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$ are good integers.
  
 
== See Also ==
 
== See Also ==

Revision as of 16:50, 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}{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$ (Error compiling LaTeX. Unknown error_msg)k+1$is odd, then write$k+1 = 2g + 9$for some integer$g$.

It follows that because$ (Error compiling LaTeX. Unknown error_msg)k \ge 74$, we must have

<cmath>g = \frac{k}{2} - 4 \ge 37 - 4 = 33.</cmath>

Thus,$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)k+1$is even, write$k+1 = 2g+2$for some integer$g$. Therefore, <cmath>g = \frac{k-1}{2} > \frac{73-1}{2} = 36 > 3,</cmath> 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$ (Error compiling LaTeX. Unknown error_msg)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=63070"