Bethan is playing a game on an $n\times n$ grid consisting of $n^2$ cells. A move consists of placing a counter in an unoccupied cell $C$ where the $2n-2$ other cells in the same row or column as $C$ contain an even number of counters. After making $M$ moves Bethan realises she cannot make any more moves. Determine the minimum value of $M$. United Kingdom, Sam Bealing
Problem
Source: 2020 RMM Shortlist C1
Tags: combinatorics, grid, RMM, RMM 2020, RMM Shortlist
09.10.2022 21:48
Ivan plays tic-tac-toe.
18.02.2023 19:53
The required minimum is $M = (n^2 + 1)/2$ if $n{}$ is odd and $M = n^2/2 + n$ if $n{}$ is even. First we show that $M{}$ can attain these bounds. For $n{}$ odd consider the configuration shown below to the left, consisting of one $(n+1)/2\times (n+1)/2$ square of counters and one $(n-1)/2\times (n-1)/2$ square of counters; each empty square has exactly $n{}$ counters in the same row or column as itself so no more counters can be placed. For even $n{}$, let $\{x, y\} = \{n/2,n/2+1\}$ where $x{}$ is odd, and consider the configuration shown above to the right, consisting of an $x \times x$ square of counters and a $y \times y$ square of counters overlapping at one cell; each empty square has exactly $x + y$ counters in the same row or column as itself, an odd number, so no more counters can be placed. To show that we can reach these configurations by a sequence of valid moves, first note that we can fill a $k \times k$ square on an empty board by filling each diagonal in turn (where we assume a diagonal ‘wraps around’, so there are $k{}$ diagonals, each consisting of $k{}$ cells). This concludes the odd $n{}$ case immediately. We can achieve the even $n{}$ case by assembling the $x \times x$ square first in the same fashion, and then the $y \times y$ square by filling the long diagonal first (since then the fact that its first cell, along with the $x-1$ cells below and the $x-1$ cells to the left, have already been given makes no difference). Now we show that the above configuration is optimal. We call a (not necessarily empty) square playable if the other $2n-2$ cells in its row and column contain an even number of tokens. We say a column or row is odd/even if it contains an odd/even number of tokens. It is clear a square is playable if and only if its row and column are either both odd or both even. Use $c_O, c_E$ to denote the number of odd/even columns and similarly $r_O, r_E$ for the rows. First, we claim $c_O = r_O$ after any sequence of moves. Note this is true when the board is empty. Any move must involve a playable square, so either turns an odd row and column to an even row and column or vice versa. This preserves the above property and so proves the claim. This means that the number of playable squares is $P = c_Or_O + c_Er_E = c_O^2 + c_E^2{}$. Now, consider the final configuration. If $n{}$ is odd then $c_O + c_E = n$ implies that $P \geqslant ((n+1)/2)^2+((n-1)/2)^2$ so we are done. If $n{}$ is even, we divide into two cases: Case 1: Assume that $c_O, c_E$ are both odd. Then in the final configuration there is a token in each playable square. However, in each row with an even number of tokens, there are $c_E$ playable squares; $c_E$ is an odd number, so there must be one more token in each even row that is not in a playable square. Similarly, there is one more token in each even column that is not in a playable square. Morover, these sets of additional tokens are disjoint, as any square in an even row and even column is playable. Hence the number of tokens is at least $P + c_E + r_E = P + 2c_E{}$. Case 2: Assume that $c_O, c_E$ are both odd. A very similar argument shows that there must be an extra token not in a playable square in each odd row and each odd column, implying the number of tokens is at least $P + cO + rO = P + 2c_O$. Thus in either case the number of tokens $M{}$ satisfies $M^2\geqslant c_O^2+c_E^2+2\min(c_O,c_E)$. As $c_O+c_E=n$ write $\{c_O,c_E\}=\{n/2+x,n/2-x\}$ where $x{}$ is a non-negative integer. Then \begin{align*}M\geqslant\left(\frac{n}{2}+x\right)^2+\left(\frac{n}{2}-x\right)^2+2\left(\frac{n}{2}-x\right)=\frac{n^2}{2}+n+2x(x-1)\geqslant\frac{n^2}{2}+n,\end{align*}since $x{}$ is an integer. This ends the proof.