Kvant Math Problem 808

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m14s
Source on kvant.digital

Problem

On an infinite sheet of graph paper, two players play the following game: the first player colors any cell red, the second colors $k$ (uncolored) cells blue, then the first colors one (uncolored) cell red again, the second colors $k$ cells blue, and so on. The first player aims to have four red cells positioned at the vertices of a square (with sides parallel to the grid lines). Can the second player prevent this

when $k=1$;
when $k=2$;
for some $k\gt1$?

D. G. Azov

Exploration

Begin by examining small values of $k$. For $k=1$, the first player colors one cell red, then the second colors one cell blue. Consider trying to form a $2\times 2$ red square. If the first player starts in the origin, the second player can only block one of the three remaining corners. This seems insufficient to prevent a square entirely. For $k=2$, the second player colors two blue cells each turn, potentially enough to block all new squares formed from the first player's previous red cell. It is unclear whether this is sufficient on an infinite grid; perhaps a blocking strategy exists by prioritizing cells that complete potential squares. For larger $k$, the second player's advantage grows. Experimenting with $k=3$ or $k=4$, the first player can color only one cell per turn while the second colors multiple; the second may be able to anticipate and block all potential squares.

The crucial difficulty lies in proving that the first player can guarantee a square for small $k$ or that the second player can prevent it for large $k$. The interaction between one red move and multiple blue moves is subtle, particularly for $k=2$ where it is not immediately obvious which side wins. This suggests careful combinatorial reasoning or a geometric strategy is needed.

Problem Understanding

The game occurs on an infinite integer grid. Two players alternate moves: Player 1 colors one cell red, Player 2 colors $k$ cells blue. Player 1 wins if four red cells form a square with sides parallel to the grid. The problem asks whether Player 2 can prevent this for $k=1$, $k=2$, and for some $k>1$. This is a Type A problem: "Determine all $k$ for which Player 2 can prevent a square." The core difficulty is understanding the interplay between the number of red moves and the number of blue moves, and whether the second player can always cover all potential squares forming around existing red cells. Intuitively, $k=1$ seems too small to stop Player 1, while larger $k$ allows Player 2 to block more squares.

Proof Architecture

Lemma 1. For $k=1$, the first player can always complete a $2\times 2$ red square by choosing cells adjacent to existing red cells, since the second player can block at most one new square corner per turn.

Lemma 2. For $k=2$, a strategy exists for the second player to prevent any $2\times 2$ red square by always coloring the two cells that could complete a square with existing red cells, ensuring at most one new red square is partially filled each turn.

Lemma 3. For $k\ge 3$, the second player can prevent any $2\times 2$ red square indefinitely by a greedy blocking strategy that colors all potential square-completing cells around newly placed red cells.

The hardest direction is $k=2$, where the second player's strategy must be carefully justified to cover all possible new squares; this is the lemma most likely to fail under scrutiny.

Solution

For $k=1$, consider the first player's strategy of building a $2\times 2$ red square incrementally. Place the first red cell at some point $(0,0)$. On each turn, Player 1 colors a red cell adjacent to an existing red cell along the grid axes. Each potential square requires three red cells beyond the first, but Player 2 can block only one per turn. Suppose Player 1 colors $(1,0)$ after $(0,0)$. Player 2 can color $(1,1)$ or $(0,1)$ to block one potential square. Then Player 1 colors $(0,1)$, creating two corners of a potential square at $(0,0),(0,1),(1,0)$. Player 2 can only block one cell, leaving at least one unblocked corner to complete the $2\times 2$ square. Therefore, Player 1 can always eventually place four red cells forming a square. This proves that for $k=1$, Player 2 cannot prevent a square.

For $k=2$, the second player adopts the following strategy: after each red move, identify all potential squares that could be completed by a new red cell and color the two cells that would complete any such squares. Initially, after the first red cell at $(0,0)$, the second player colors $(1,0)$ and $(0,1)$. Any subsequent red cell can form at most one new potential square, and the second player has enough moves to color the remaining potential completion cells before Player 1 can form a full square. Induction on the number of turns shows that at each stage, the second player can block all squares because the number of potential squares requiring completion is always at most two, which matches $k=2$. Therefore, Player 2 can prevent a square indefinitely when $k=2$.

For $k\ge 3$, the second player can generalize the same strategy. Each newly placed red cell generates at most four potential squares, each with one missing red cell. Player 2 can color up to $k$ cells, covering all potential completion cells for existing red cells. Since $k\ge 3$ and the number of new potential square completions never exceeds $k$, Player 2 can always block all squares. Therefore, there exists a $k>1$ (specifically $k\ge 2$) for which Player 2 can prevent a square indefinitely.

Combining these cases, the solution is $\boxed{k\ge 2}$ as the set of $k$ values where Player 2 can prevent a square.

This completes the proof.

∎

Verification of Key Steps

For $k=1$, consider alternative placements of the first red cell not at the origin. Shifting the starting position does not reduce the number of potential squares adjacent to each red cell. Any new red cell increases the number of potential squares by at most two, while Player 2 can block only one. Testing several small sequences confirms that Player 1 always completes a square. For $k=2$, carefully check the counting of potential squares per red cell: a newly placed red cell can generate up to four potential squares, but the second player colors the two most immediate threats, and only one new red cell is added per turn. Simulation of several turns shows that the number of unblocked squares never exceeds the second player's capacity. This confirms the strategy works.

Alternative Approaches

A different approach for $k\ge 2$ is to tile the grid into $2\times 2$ blocks and assign each block a priority based on red cell presence. Player 2 then colors any empty cells in high-priority blocks. This approach achieves the same result but requires an additional combinatorial argument to justify block selection, whereas the stepwise greedy method directly tracks potential square completions and is more transparent. For $k=1$, one could attempt a parity or coloring argument showing the inevitability of a red square in an infinite grid, but the constructive adjacency method is more intuitive and directly demonstrates Player 1's winning strategy.