Putnam 2005, Problem A-1

Show that every positive integer is a sum of one or more numbers of the form $2^r 3^s$, where $r$ and $s$ are nonnegative integers and no summand divides another. (For example, $23 = 9 + 8 + 6$.)

Solution:
We proceed by induction, with base case \(1 = 2^0 3^0\). Suppose all integers less than \(n-1\) can be represented. If \(n\) is even, then we can take a representation of \(n/2\) and multiply each term by 2 to obtain a representation of \(n\). If \(n\) is odd, put \(m = \lfloor \log_3 n \rfloor\), so that \(3^m \leq n < 3^{m+1}\). If \(3^m = n\), we are done. Otherwise, choose a representation \((n - 3^m)/2 = s_1 + \cdots + s_k\) in the desired form. Then
\[
n = 3^m + 2s_1 + \cdots + 2s_k,
\]
and clearly none of the \(2s_i\) divide each other or \(3^m\). Moreover, since \(2s_i \leq n - 3^m < 3^{m+1} - 3^m\), we have \(s_i < 3^m\), so \(3^m\) cannot divide \(2s_i\) either. Thus \(n\) has a representation of the desired form in all cases, completing the induction.

Remarks: This problem is originally due to Paul Erdős. Note that the representations need not be unique: for instance,
\[
11 = 2 + 9 = 3 + 8.
\]