
Problem 1. Let $k \leq 2022$ be a positive integer. Alice and Bob play a game on a $2022 \times 2022$ board. Initially, all cells are white. Alice starts and the players alternate. In her turn, Alice can either color one white cell in red or pass her turn. In his turn, Bob can either color a $k \times k$ square of white cells in blue or pass his turn. Once both players pass, the game ends and the person who colored more cells wins (a draw can occur).

For each $1 \leq k \leq 2022$, determine which player (if any) has a winning strategy.

(David Hruška)


Solution. Answer: For $k \in\{1,3,337,1011\}$ the game ends in a draw, otherwise Alice wins.

Fix $k$. Number the rows from top to bottom and the columns from left to right using numbers $1, \ldots, 2022$. We say that a cell is critical if its row-number and column-number are both divisible by $k$. Note that Bob colors exactly one critical cell in each his turn. Let $c=\lfloor 2022 / k\rfloor^{2}$ be the number of critical cells.

We distinguish 3 cases based on the value 2022/k.

(1) $2022 / k \notin \mathbb{Z}$. Then Alice can force a win, e.g. by primarily coloring the critical cells (and then coloring the rest): If she follows this strategy then Bob will color a $k \times k$ square in at most $c / 2$ of his turns, so in total he will color $\frac{1}{2} c \cdot k^{2}<\frac{1}{2} \cdot 2022^{2}$ cells.

(2) $2022 / k$ is an odd integer. Then Alice can force a win by the same strategy: In this case $c$ is odd, so Bob will color a $k \times k$ square in at most $\lfloor c / 2\rfloor<\frac{1}{2} c$ of his turns, so in total he will color strictly less than $\frac{1}{2} c \cdot k^{2}=\frac{1}{2} \cdot 2022^{2}$ cells.

(3) $2022 / k$ is an even integer. Then both players can guarantee at least a draw: Alice by the above strategy, Bob by always coloring a $k \times k$ square whose bottom right corner cell is critical. Since in this case $c$ is even and each Alice's move prevents Bob from coloring at most 1 such square, using this strategy he will color at least $\frac{1}{2} c \cdot k^{2}=\frac{1}{2} \cdot 2022^{2}$ cells.

Since $2022=2 \cdot 3 \cdot 337$, case (3) occurs if and only if $k \in\{1,3,337,1011\}$.
