Ana and Beto play on a grid of $2022 \times 2022$. Ana colors the sides of some squares on the board red, so that no square has two red sides that share a vertex. Next, Bob must color a blue path that connects two of the four corners of the board, following the sides of the squares and not using any red segments. If Beto succeeds, he is the winner, otherwise Ana wins. Who has a winning strategy?
Problem
Source: 2022 Cono Sur #4
Tags: combinatorics, Game Theory
09.08.2022 23:04
Beto has a winning strategy. We use sides and edges interchangeably. Let the edges on the outside of the grid be called "walls". From the bottom left corner, Beto draws a blue path $B_1$ going only up and right, avoiding red edges. Note that, from a vertex, if both the up and right edges exist, then it is always possible to go either up or right since they cannot both be coloured red (otherwise a square would exist where red edges share a vertex). The only way Beto cannot continue his path is if the up or right edges do not exist, i.e. his path has hit the upper or rightmost wall. WLOG, assume $B_1$ hits the righmost wall and ends there (otherwise reflect the grid over the diagonal). Then, Beto can draw a blue path $B_2$ from the bottom right corner going only up and left, avoiding red edges. Similar to before, this path can only end when it hits the upper or leftmost wall. But then it is clear that the paths $B_1$ and $B_2$ intersect, hence Beto can draw a blue path from the bottom left corner to the bottom right corner, solving the problem.