IMO 2010 Problem 5

A problem that I refused to get any hint for in the last 8 years! Of course usually I just gave it some thought for a couple of minutes and then moved on, until now...

===============

Each of the six boxes \(B_1\), \(B_2\), \(B_3\), \(B_4\), \(B_5\), \(B_6\) initially contains one coin. The following operations are allowed.

Type 1) Choose a non-empty box \(B_j\), \(1\leq j \leq 5\), remove one coin from \(B_j\) and add two coins to \(B_{j+1}\).

Type 2) Choose a non-empty box \(B_k\), \(1\leq k \leq 4\), remove one coin from \(B_k\) and swap the contents (maybe empty) of the boxes \(B_{k+1}\) and \(B_{k+2}\).

Determine if there exists a finite sequence of operations of the allowed types, such that the five boxes \(B_1\), \(B_2\), \(B_3\), \(B_4\), \(B_5\) become empty, while box \(B_6\) contains exactly \(2010^{2010^{2010}}\) coins.

Proposed by Hans Zantema, Netherlands

===============

Comment:

Until the day I solved it, I thought the answer is no -- and until the day before I solved it, I thought it's because \(2010^{2010^{2010}}\) is too large. Then I found it's not, so I turned to number theory and invariant to prove it's not possible, as almost certainly the answer to this kind of problem is no in IMO. But not this time! This is why it's a really hard P2/5 problem and played a crucial role in determining competition result in that year.

===============

Solution:

Yes, we can obtain the coins as described.

Define \(N=2010^{2010^{2010}}\) and \((a_1,\ldots,a_k,b\}\) as a partial sequence \(a_1,\ldots,a_k\) followed by \(b\) zeros where the last item, \(a_k\) if \(b=0\) or else \(0\), is the number of coins in \(B_6\).

When determining the maximum coins that \(B_6\) can end up with, it is convienient to consider function \(g_k(n)\) defined such that we can convert \((n,k\}\) to \((0,g_k(n),k-1\}\) without involving numbers preceding the partial sequence. In the language of bin and coin, starting with \(n\) coins followed by \(k\) empty bins, we can end up with \(g_k(n)\) coins followed by \(k-1\) empty bins without touching any prior bin.

If \(n=1\), \(g_k(n)=2\); otherwise \(g_k(n)=g_{k-1}^{(n-1)}(2)\). This is because

\((n,k\}\)
\((n-1,2,k-1\}\)
\((n-1,0,g_{k-1}(2),k-2\}\)
\((n-2,g_{k-1}(2),k-1\}\)
\(\vdots\)

And we get \(g_1(n)=2n\), \(g_2(n)=2^n\), and \(g_3(n)=2^{2^{2^{\cdots}}}\) with exactly \(n\) copies of \(2\). How big is \(N\) written in \(g_3(\bullet)\)? Notice \(\log_2^{(n)}g_3(n)=1\), and

\(\log_2{N}\lt11\times2010^{2010}\)
\(\log_2^{(2)}{N}\lt 4+11\times2010\lt 16\times2010\)
\(\log_2^{(3)}{N}\lt 4+11=15\lt16\)
\(\log_2^{(4)}{N}\lt 4\)
\(\log_2^{(5)}{N}\lt 2\)
\(\log_2^{(6)}{N}\lt 1\)

Thus \(N\lt g_3(6)\), and we can obtain the desired result with the following

\((1,1,1,1,1,1)\)
\((3,1,1,1,1)\)
\((2,3,1,1,1)\)
\((2,2,3,1,1)\)
\((2,2,2,3,1)\)
\((2,2,2,0,7)\)
\((2,2,1,7,0)\)
\((2,2,0,9,0)\)
\((2,1,9,0,0)\)
\((2,0,11,0,0)\)
\((1,11,0,0,0)\)
\(\vdots\)
\((1,0,g_3(11),0,0)\)
\(\vdots\)
\((1,0,\frac{N}{4},0,0)\)
\(\vdots\)
\((1,0,0,0,N)\)
\((0,0,0,0,N)\)