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

1978 USAMO Problems/Problem 3

Revision as of 16:51, 14 August 2014 by Suli (talk | contribs) (→‎Solution)

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 $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=63073"