Ana and Beto play the following game on a grid. First Ana colors some unit segments on the grid red, so that no cell has two red sides who share a vertex. Next, Beto must draw a blue path that joins two of the four corners of the grid, following the sides of the grid and without using any red segments. If Beto succeeds, he is the winner; otherwise, Ana wins. Who has a winning strategy?
Solution
We will show that Beto has a winning strategy. We will prove that he can connect the bottom left corner with the bottom right or the top left corner.
We say that a row is *full red* if every vertical line in it is red.
| R | R | R | | | | R | R | R |
|---|---|---|---|---|---|---|---|---|
Analogously, we say that a column is full red if every horizontal line in it is red. We cannot have a full red row and column since this would imply that a cell has all its sides red.
We assume that we do not have a full red row. In this case we will prove that Beto can connect the bottom left corner with the top left corner.
The plan is to move through the left side of the grid. We show that if the path has reached one vertex in it then it can reach the next one (the one immediately above it). Consider the leftmost vertical line in the row that is not red (there is at least one, because the row is not full red).
| R | R | not R |
|---|---|-------|
The cells to the left of it have a vertical red line so the horizontal lines in it are not red. Thus we can connect the vertex through these segments and the one that we know is not red.
| R | R | not R |
|---|---|-------|
Therefore, proceeding in this way Beto can connect the bottom left corner with the top left corner.
Analogously, if we do not have a full red column then Beto can connect the bottom left corner with the bottom right corner.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.