International Mathematical Olympiad

Solution 1. We will solve a more general problem, replacing the row of 9 cells with a row of $k$ cells, where $k$ is a positive integer. Denote by $m(n,k)$ the maximum possible number of moves Sir Alex can make starting with a row of $k$ empty cells, and ending with one cell containing the number $2^n$ and all the other $k-1$ cells empty. Call an operation of type (1) an insertion, and an operation of type (2) a merge. Only one move is possible when $k=1$, so we have $m(n,1)=1$. From now on we consider $k⩾2$, and we may assume Sir Alex's last move was a merge. Then, just before the last move, there were exactly two cells with the number $2^{n-1}$, and the other $k-2$ cells were empty. Paint one of those numbers $2^{n-1}$ blue, and the other one red. Now trace back Sir Alex's moves, always painting the numbers blue or red following this rule: if $a$ and $b$ merge into $c$, paint $a$ and $b$ with the same color as $c$. Notice that in this backward process new numbers are produced only by reversing merges, since reversing an insertion simply means deleting one of the numbers. Therefore, all numbers appearing in the whole process will receive one of the two colors. Sir Alex's first move is an insertion. Without loss of generality, assume this first number inserted is blue. Then, from this point on, until the last move, there is always at least one cell with a blue number. Besides the last move, there is no move involving a blue and a red number, since all merges involve numbers with the same color, and insertions involve only one number. Call an insertion of a blue number or merge of two blue numbers a blue move, and define a red move analogously. The whole sequence of blue moves could be repeated on another row of $k$ cells to produce one cell with the number $2^{n-1}$ and all the others empty, so there are at most $m(n-1,k)$ blue moves. Now we look at the red moves. Since every time we perform a red move there is at least one cell occupied with a blue number, the whole sequence of red moves could be repeated on a row of $k-1$ cells to produce one cell with the number $2^{n-1}$ and all the others empty, so there are at most $m(n-1,k-1)$ red moves. This proves that $$m(n,k)⩽m(n-1,k)+m(n-1,k-1)+1$$ On the other hand, we can start with an empty row of $k$ cells and perform $m(n-1,k)$ moves to produce one cell with the number $2^{n-1}$ and all the others empty, and after that perform $m(n-1,k-1)$ moves on those $k-1$ empty cells to produce the number $2^{n-1}$ in one of them, leaving $k-2$ empty. With one more merge we get one cell with $2^n$ and the others empty, proving that $$m(n,k)⩾m(n-1,k)+m(n-1,k-1)+1.$$ It follows that $$\begin{array}{c}m(n,k)=m(n-1,k)+m(n-1,k-1)+1,\end{array}\text{\hspace{1em}(1)}$$ for $n⩾1$ and $k⩾2$. If $k=1$ or $n=0$, we must insert $2^n$ on our first move and immediately get the final configuration, so $m(0,k)=1$ and $m(n,1)=1$, for $n⩾0$ and $k⩾1$. These initial values, together with the recurrence relation (1), determine $m(n,k)$ uniquely. Finally, we show that $$\begin{array}{c}m(n,k)=2\sum _{j=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{j}\right)-1,\end{array}\text{\hspace{1em}(2)}$$ for all integers $n⩾0$ and $k⩾1$. We use induction on $n$. Since $m(0,k)=1$ for $k⩾1$, (2) is true for the base case. We make the induction hypothesis that (2) is true for some fixed positive integer $n$ and all $k⩾1$. We have $m(n+1,1)=1=2\left(\genfrac{}{}{0ex}{}{n+1}{0}\right)-1$, and for $k⩾2$ the recurrence relation (1) and the induction hypothesis give us $$\begin{array}{rl}& m(n+1,k)=m(n,k)+m(n,k-1)+1=2\sum _{j=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{j}\right)-1+2\sum _{j=0}^{k-2}\left(\genfrac{}{}{0ex}{}{n}{j}\right)-1+1\\ & =2\sum _{j=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{j}\right)+2\sum _{j=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{j-1}\right)-1=2\sum _{j=0}^{k-1}\left(\left(\genfrac{}{}{0ex}{}{n}{j}\right)+\left(\genfrac{}{}{0ex}{}{n}{j-1}\right)\right)-1=2\sum _{j=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n+1}{j}\right)-1,\end{array}$$ which completes the proof.

Solution 2. Define merges and insertions as in Solution 1. After each move made by Sir Alex we compute the number $N$ of empty cells, and the sum $S$ of all the numbers written in the cells. Insertions always increase $S$ by some power of 2, and increase $N$ exactly by 1. Merges do not change $S$ and decrease $N$ exactly by 1. Since the initial value of $N$ is 0 and its final value is 1, the total number of insertions exceeds that of merges by exactly one. So, to maximize the number of moves, we need to maximize the number of insertions. We will need the following lemma. Lemma. If the binary representation of a positive integer $A$ has $d$ nonzero digits, then $A$ cannot be represented as a sum of fewer than $d$ powers of 2. Moreover, any representation of $A$ as a sum of $d$ powers of 2 must coincide with its binary representation. Proof. Let $s$ be the minimum number of summands in all possible representations of $A$ as sum of powers of 2. Suppose there is such a representation with $s$ summands, where two of the summands are equal to each other. Then, replacing those two summands with the result of their sum, we obtain a representation with fewer than $s$ summands, which is a contradiction. We deduce that in any representation with $s$ summands, the summands are all distinct, so any such representation must coincide with the unique binary representation of $A$, and $s=d$. Now we split the solution into a sequence of claims. Claim 1. After every move, the number $S$ is the sum of at most $k-1$ distinct powers of 2. Proof. If $S$ is the sum of $k$ (or more) distinct powers of 2, the Lemma implies that the $k$ cells are filled with these numbers. This is a contradiction since no more merges or insertions can be made. Let $A(n,k-1)$ denote the set of all positive integers not exceeding $2^n$ with at most $k-1$ nonzero digits in its base 2 representation. Since every insertion increases the value of $S$, by Claim 1, the total number of insertions is at most $|A(n,k-1)|$. We proceed to prove that it is possible to achieve this number of insertions. Claim 2. Let $A(n,k-1)=\{a_1,a_2,\dots ,a_m\}$, with $a_1<a_2<\cdots <a_m$. If after some of Sir Alex's moves the value of $S$ is $a_j$, with $j\in \{1,2,\dots ,m-1\}$, then there is a sequence of moves after which the value of $S$ is exactly $a_{j+1}$. Proof. Suppose $S=a_j$. Performing all possible merges, we eventually get different powers of 2 in all nonempty cells. After that, by Claim 1 there will be at least one empty cell, in which we want to insert $a_{j+1}-a_j$. It remains to show that $a_{j+1}-a_j$ is a power of 2. For this purpose, we notice that if $a_j$ has less than $k-1$ nonzero digits in base 2 then $a_{j+1}=a_j+1$. Otherwise, we have $a_j=2^{b_{k-1}}+\cdots +2^{b_2}+2^{b_1}$ with $b_1<b_2<\cdots <b_{k-1}$. Then, adding any number less than $2^{b_1}$ to $a_j$ will result in a number with more than $k-1$ nonzero binary digits. On the other hand, $a_j+2^{b_1}$ is a sum of $k$ powers of 2, not all distinct, so by the Lemma it will be a sum of less than $k$ distinct powers of 2. This means that $a_{j+1}-a_j=2^{b_1}$, completing the proof. Claims 1 and 2 prove that the maximum number of insertions is $|A(n,k-1)|$. We now compute this number. Claim 3. $|A(n,k-1)|={\sum }_{j=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. Proof. The number $2^n$ is the only element of $A(n,k-1)$ with $n+1$ binary digits. Any other element has at most $n$ binary digits, at least one and at most $k-1$ of them are nonzero (so they are ones). For each $j\in \{1,2,\dots ,k-1\}$, there are $\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ such elements with exactly $j$ binary digits equal to one. We conclude that $|A(n,k-1)|=1+{\sum }_{j=1}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{j}\right)={\sum }_{j=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. Recalling that the number of insertions exceeds that of merges by exactly 1, we deduce that the maximum number of moves is $2{\sum }_{j=0}^{k-1}\left(\genfrac{}{}{0ex}{}{n}{j}\right)-1$.