Let $a, b, n$ be positive integers such that $a+b \leq n^{2}$. Alice and Bob play a game on an (initially uncoloured) $n \times n$ grid as follows:

- First, Alice paints $a$ cells green.
- Then, Bob paints $b$ other (i.e. uncoloured) cells blue.

Alice wins if she can find a path of non-blue cells starting with the bottom left cell and ending with the top right cell (where a path is a sequence of cells such that any two consecutive ones have a common side), otherwise Bob wins. Determine, in terms of $a, b$ and $n$, who has a winning strategy. Answer: If $a \geq \min (2 b, 2 n-1)$, Alice wins, otherwise Bob wins.
![](https://cdn.mathpix.com/cropped/2024_11_22_358eef26f8d72df36f1eg-08.jpg?height=413&width=426&top_left_y=179&top_left_x=501)

Figure 7
![](https://cdn.mathpix.com/cropped/2024_11_22_358eef26f8d72df36f1eg-08.jpg?height=413&width=418&top_left_y=179&top_left_x=1227)

Figure 8
If $a \geq 2 n-1$, Alice can win, for example by painting all the cells in the leftmost column and the topmost row green, ensuring that there will be a green path (Fig. 77).
If $2 n-1 > a \geq 2 b$, Alice can also win. Indeed, note that $n > b$, so Alice can make sure to color (at least) the bottommost $b$ cells in the leftmost column and the rightmost $b$ cells in the topmost row green. There are now $b+1$ disjoint paths from some green square in the leftmost column to some green square in the topmost row (Fig. 8d), so there is no way for Bob to block all of the paths.
If however $a < \min (2 b, 2 n-1)$, Bob wins. Indeed, note that $\min (2 b, 2 n-1)$ is the number of all descending diagonals of length at most $b$. Hence after Alice has made her move, there must still be some of these diagonals with no green cells in it. Bob can color all cells in it blue and win.
Hence Alice wins iff $a \geq \min (2 b, 2 n-1)$.