# 1978 USAMO Problems/Problem 3

## 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.