New Zealand Mathematical Olympiad

Solution:
Let $a_{i,j}$ be the number of tokens in the square in the $i^{\mathrm{th}}$ row and $j^{\mathrm{th}}$ column, where the first row is the topmost row and the first column is the leftmost column. Furthermore let $b$ denote the number of tokens in the bag. We define a monovariant as follows.
$$m = \frac{3b}{2} + \sum_{i = 1}^{8}\sum_{j = 1}^{8}2^{16 - i - j}a_{i,j}$$
This either stays the same, or decreases after each move, because:
- If Ross plays a type 1 move, then $a_{i,j}$ decreases by 1 and $a_{i,j + 1}$ increases by 2 for some $i,j$. Thus $m$ changes by
$$m' - m = 2^{16 - i - j}(-1) + 2^{16 - i - (j + 1)}(+2)$$
$$\qquad = 0.$$
Hence $m$ stays the same after type 1 moves.
- If Ross plays a type 2 move, then $a_{i,j}$ decreases by 1 and $a_{i + 1,j}$ increases by 2 for some $i,j$. Thus $m$ changes by
$$m' - m = 2^{16 - i - j}(-1) + 2^{16 - (i + 1) - j}(+2)$$
$$\qquad = 0.$$
Hence $m$ stays the same after type 2 moves.
- If Ross plays a type 3 move, then $b$ increases by 2 while $a_{i,j}$ and $a_{i',j'}$ both decrease by 1 for some $i,j,i',j'$.
$$m' - m = \frac{3}{2} (+2) + 2^{16 - i - j}(-1) + 2^{16 - i' - j'}(-1)$$
$$\qquad \leq \frac{3}{2} (+2) + 2^{0}(-1) + 2^{1}(-1)$$
$$\qquad = 0.$$
Hence $m$ stays the same or decreases after these moves.
At the beginning,
$$m = \frac{3b}{2} + \sum_{i = 1}^{8}\sum_{j = 1}^{8}2^{16 - i - j}a_{i,j}$$
$$\qquad = 0 + \sum_{i = 1}^{8}\sum_{j = 1}^{8}2^{16 - i - j}$$
$$\qquad = 0 + 2^{16}\sum_{i = 1}^{8}2^{-i}\sum_{j = 1}^{8}2^{-j}$$
$$\qquad = 0 + 2^{16}\sum_{i = 1}^{8}2^{-i}(1 - 2^{-8})$$
$$\qquad = 0 + 2^{16}(1 - 2^{-8})(1 - 2^{-8})$$
$$\qquad = 65025.$$
Therefore at the end we must have $m \leq 65025$. Thus we obtain
$$\frac{3}{2} b \leq m \leq 65025 \iff b \leq 43350.$$
To obtain equality we simply need to perform any strategy in which:
- Moves of type 3 are only ever performed on either $a_{7,8}$ and $a_{8,8}$, or $a_{8,7}$ and $a_{8,8}$.
- The chessboard is empty at the end of the game.
Now consider a strategy in which we start by applying all moves of type 1 and type 2, until $a_{i,j} = 0$ for all squares except for $a_{7,8}$, $a_{8,7}$ and $a_{8,8}$. At this point we will have $a_{8,8} = 1$ and since $m$ is invariant,
$$65025 = 0 + a_{8,8} + 2a_{7,8} + 2a_{8,7} = 1 + 2(a_{7,8} + a_{8,7}).$$
Thus $a_{7,8} + a_{8,7} = 32512$. Now perform 10837 further moves (either type 1 on $a_{7,8}$ or type 2 on $a_{8,7}$) so that we end up with a state in which:
$$\cdot a_{7,8} + a_{8,7} = 32512 - 10837 = 21675,\mathrm{and}$$
$$\cdot a_{8,8} = 1 + 2\times 10837 = 21675.$$
From here we can finish by performing 21675 type 3 moves and obtain $b = 2 \times 21675 = 43350$ tokens in the bag.

Solution:
First note that we may assume that all type 3 moves are performed after all the type 1 and type 2 moves have been made. WLOG We may also assume that all moves (type 1 and 2) into square $(8,8)$ occur all other type 1 and type 2 moves.
Claim: In an optimal solution no type 3 move is made except from a pair including the lower right corner.
Proof: If we make one elsewhere, then we could first double each of those coins and move them to another adjacent pair of squares. Then we could perform two type 3 moves (in this new adjacent pair of squares) and get result in $+2$ more coins in the bag. $\square$
From here it is clear that all the coins (except for the one that starts in $(8,8)$) must eventually move to either $(7,8)$ or $(8,7)$. So there will be a point in which there is:
one coin on $(8,8)$, $A$ coins on $(7,8)$, $B$ coins on $(8,7)$, and all other squares are empty.
A coin starting in square $(x,y)$ will need to double $(8 + 7 - x - y)$ times on its way to either $(7,8)$ or $(8,7)$. Therefore
$$A + B = \sum_{(x,y)\neq (8,8)}2^{8 + 7 - x - y} = 2^{15}\sum_{x = 1}^{8}2^{-x}\sum_{y = 1}^{8}2^{-y} - 2^{-1} = 2^{-15}\left(\frac{2^{-9} - 2^{1}}{2^{-1} - 1}\right)^{2} - \frac{1}{2} = 32512.$$
Now let $m$ be the number of type 1 and type 2 moves we make before we finish the game by making as many type 3 moves as possible.
After these $m$ moves there will be $2m + 1$ coins on square $(8,8)$.
After these $m$ moves there will be a total of $A + B - m = 32512 - m$ coins on squares $(7,8)$ and $(8,7)$.
So the maximum number of type 3 moves we can make is
$$M = \min \left(2m + 1,32512 - m\right).$$
If $m \leq 10837$ then $M = 2m + 1 \leq 21675$. If $m \geq 10837$ then $M = 32512 - m \leq 21675$. Hence the maximum occurs when $m = 10837$ and so $M = 21675$ type 3 moves are made.

From here we can finish by performing 21675 type 3 moves and obtain $b = 2 \times 21675 = 43350$ tokens in the bag.