Putnam 2015, Problem B-2

Given a list of the positive integers $1,2,3,4,\ldots$, take the first three numbers $1,2,3$ and their sum $6$ and cross all four numbers off the list. Repeat with the three smallest remaining numbers $4,5,7$ and their sum $16$. Continue in this way, crossing off the three smallest remaining numbers and their sum, and consider the sequence of sums produced: $6,16,27,36,\ldots$. Prove or disprove that there is some number in the sequence whose base $10$ representation ends with $2015$.

Solution:
We will prove that 42015 is such a number in the sequence. Label the sequence of sums \(s_0, s_1, \ldots\), and let \(a_n, b_n, c_n\) be the summands of \(s_n\) in ascending order. We prove the following two statements for each nonnegative integer \(n\):

(a)\(_n\) The sequence
\[
a_{3n}, b_{3n}, c_{3n}, a_{3n+1}, b_{3n+1}, c_{3n+1}, a_{3n+2}, b_{3n+2}, c_{3n+2}
\]
is obtained from the sequence \(10n + 1, \ldots, 10n + 10\) by removing one of \(10n + 5, 10n + 6, 10n + 7\).

(b)\(_n\) We have
\[
s_{3n} = 30n + 6, \quad s_{3n+1} \in \{30n + 15, 30n + 16, 30n + 17\}, \quad s_{3n+2} = 30n + 27.
\]

These statements follow by induction from the following simple observations:

- by computing the table of values
\[
\begin{array}{c|ccc}
n & a_n & b_n & c_n & s_n \\
\hline
0 & 1 & 2 & 3 & 6 \\
1 & 4 & 5 & 7 & 16 \\
2 & 8 & 9 & 10 & 27 \\
\end{array}
\]
we see that (a)\(_0\) holds;

- (a)\(_n\) implies (b)\(_n\);

- (a)\(_n\) and (b)\(_1, \ldots, (b)_n\) together imply (a)\(_{n+1}\).

To produce a value of \(n\) for which \(s_n \equiv 2015 \pmod{10000}\), we take \(n = 3m + 1\) for some nonnegative integer \(m\) for which \(s_{3m+1} = 30m + 15\). We must also have \(30m \equiv 2000 \pmod{10000}\), or equivalently \(m \equiv 400 \pmod{1000}\). By taking \(m = 1400\), we ensure that \(m \equiv 2 \pmod{3}\), so \(s_m = 10m + 7\); this ensures that \(s_n\) does indeed equal \(30m + 15 = 42015\), as desired.

Remark: With a bit more work, we can give a complete description of \(s_n\), and in particular find the first term in the sequence whose decimal expansion ends in 2015. Define the function on nonnegative integers
\[
f(n) = s_{3n+1} - (30n + 16)
\]
which takes values in \(\{-1, 0, 1\}\); we then have
\[
f(n) = \begin{cases} 0 & n \equiv 0 \pmod{3} \\ -f((n-1)/3) & n \equiv 1 \pmod{3} \\ -1 & n \equiv 2 \pmod{3}. \end{cases}
\]
Consequently, if we write \(n\) in base 3, then \(f(n) = 0\) unless the expansion ends with 2 followed by a string of 1s of length \(k \geq 0\), in which case \(f(n) = (-1)^{k+1}\). In this notation, we have \(s_n \equiv 2015 \pmod{10000}\) if and only if \(n = 3m + 1\) for some nonnegative integer \(m\) for which \(m \equiv 400 \pmod{1000}\) and \(f(m) = -1\). Since \(400 = 112211_3\), the first such term in the sequence is in fact \(s_{1201} = 12015\).