IRL_ABooklet

We denote by $m_{i,j}$ the number of marbles in Box $B_i$ after $j$ moves, and we define the associated sum $s_j$ by $$s_j:=\sum _{i=1}^{\infty }{m}_{i,j}{2}^{i-1}.$$ We have $s_0=0$ and each $s_j-s_{j-1}$ is non-negative. In fact, $s_j-s_{j-1}$ equals: $$\begin{array}{c}3\\ 1+2^{M-1}\\ 0\end{array}\}\text{if the }j\text{’th move is}\begin{array}{c}A\\ B\\ C_k\end{array}\}(11)$$ It follows that $s_j>1$ for all $j>0$, and that a necessary condition to win after $j$ steps is that $s_j$ is a power of 2. Suppose $M$ is even. Then, $1+2^{M-1}$ is a multiple of 3, so it follows inductively from (11) that $s_j$ is divisible by 3 for all $j$. We deduce that $s_j$ is never a power of 2. Thus, we cannot win the $M$-game if $M$ is even. Suppose instead that $M$ is odd. Then $1+2^{M-1}\equiv 2(\mathrm{mod}3)$. If we first do Move $B$ and then repeatedly do Move $A$, the numbers $s_j$ take on all values $v\ge v_0:=1+2^{M-1}$ that are congruent to 2 (mod 3). We eventually reach a power of 2; in fact, using these moves, $s_j$ hits each odd power of 2 exceeding $v_0$. Suppose that $$s_j=\sum _{i=1}^{\infty }{m}_{i,j}{2}^{i-1}$$ equals $2^P$ for some $P\in \mathbb{N}$. All our subsequent moves will be $C$-moves (meaning moves of the form $C_k$) and we continue until we can no longer perform a $C$-move. Each $C$-move lowers the total number of marbles by 1, so eventually no further $C$-moves are possible. Note though that the sum stays unchanged according to (11), so it is still $2^P$. Suppose that after $J\ge j$ steps, we can go no further. This implies that $m_{i,J}\le 1$ for all $i$. Let $N$ be the largest value of $i$ such that $m_{i,J}=1$, and suppose we are not in a winning position i.e. $m_{i,J}=1$ for at least one value of $i<N$. Then $$2^{N-1}<s_J=\sum _{i=1}^N{m}_{i,J}{2}^{i-1}\le \sum _{i=1}^N{2}^{i-1}=2^N-1.$$ This contradicts the assumption that $s_J$ is a power of 2. We conclude that the sequence of $C$-moves can end only when we reach a winning position. We have shown that we can win if and only if $M$ is odd, and we have an algorithm for winning when it is possible.