4. Problem: On a table, there is an empty bag and a chessboard containing exactly one token on each square. Next to the table is a large pile that contains an unlimited supply of tokens. Using only the following types of moves what is the maximum possible number of tokens that can be in the bag?
- Type 1: Choose a non-empty square on the chessboard that is not in the rightmost column. Take a token from this square and place it, along with one token from the pile, on the square immediately to its right.
- Type 2: Choose a non-empty square on the chessboard that is not in the bottommost row. Take a token from this square and place it, along with one token from the pile, on the square immediately below it.
- Type 3: Choose two adjacent non-empty squares. Remove a token from each and put them both into the bag.
Solution A: (Ishan Nath)
Let $a_{i, j}$ be the number of tokens in the square in the $i^{\text {th }}$ row and $j^{\text {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{3 b}{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
$$
\begin{aligned}
m^{\prime}-m & =2^{16-i-j}(-1)+2^{16-i-(j+1)}(+2) \\
& =0 .
\end{aligned}
$$

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
$$
\begin{aligned}
m^{\prime}-m & =2^{16-i-j}(-1)+2^{16-(i+1)-j}(+2) \\
& =0 .
\end{aligned}
$$

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^{\prime}, j^{\prime}}$ both decrease by 1 for some $i, j, i^{\prime}, j^{\prime}$.
$$
\begin{aligned}
m^{\prime}-m & =\frac{3}{2}(+2)+2^{16-i-j}(-1)+2^{16-i^{\prime}-j^{\prime}}(-1) \\
& \leq \frac{3}{2}(+2)+2^{0}(-1)+2^{1}(-1) \\
& =0 .
\end{aligned}
$$

Hence $m$ stays the same or decreases after these moves. At the beginning,
$$
\begin{aligned}
m & =\frac{3 b}{2}+\sum_{i=1}^{8} \sum_{j=1}^{8} 2^{16-i-j} a_{i, j} \\
& =0+\sum_{i=1}^{8} \sum_{j=1}^{8} 2^{16-i-j} \\
& =0+2^{16} \sum_{i=1}^{8} 2^{-i} \sum_{j=1}^{8} 2^{-j} \\
& =0+2^{16} \sum_{i=1}^{8} 2^{-i}\left(1-2^{-8}\right) \\
& =0+2^{16}\left(1-2^{-8}\right)\left(1-2^{-8}\right) \\
& =65025
\end{aligned}
$$

Therefore at the end we must have $m \leq 65025$. Thus we obtain
$$
\frac{3}{2} b \leq m \leq 65025 \Longleftrightarrow 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}+2 a_{7,8}+2 a_{8,7}=1+2\left(a_{7,8}+a_{8,7}\right) .
$$

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:
- $a_{7,8}+a_{8,7}=32512-10837=21675$, and
- $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 B: (Michael Albert)
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 it's 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 $2 m+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 (2 m+1,32512-m) .
$$

If $m \leq 10837$ then $M=2 m+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.