Two players, and , play the following game on an infinite grid of unit squares, all initially colored white. The players take turns starting with . On 's turn, selects one white unit square and colors it blue. On 's turn, selects two white unit squares and colors them red. The players alternate until decides to end the game. At this point, gets a score, given by the number of unit squares in the largest (in terms of area) simple polygon containing only blue unit squares. What is the largest score can guarantee?
(A simple polygon is a polygon (not necessarily convex) that does not intersect itself and has no holes.)
Solution
It is clear that can guarantee a score of squares. We will show that has a strategy to limit blue to squares, thus solving the problem.
Partition the grid into 2x2 squares. Red's strategy is as follows:
- If plays in a 2x2 square, play the two adjacent squares to 's square that are not in the 2x2 square.
- If one (or both) of these moves are blocked, instead play a square a megaparsec away from the rest of the moves. This move can only benefit you and will not change the outcome of the game.
By induction, it is clear that no two blue squares that are adjacent are not in the same 2x2 square. Thus, we conclude that has limited blue to a maximum score of , and the proof is complete.
~mathboy100
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.