Difference between revisions of "2023 USAJMO Problems/Problem 4"
(→Problem) |
(→Problem) |
||
| Line 3: | Line 3: | ||
Two players, <math>B</math> and <math>R</math>, play the following game on an infinite grid of unit squares, all initially colored white. The players take turns starting with <math>B</math>. On <math>B</math>'s turn, <math>B</math> selects one white unit square and colors it blue. On <math>R</math>'s turn, <math>R</math> selects two white unit squares and colors them red. The players alternate until <math>B</math> decides to end the game. At this point, <math>B</math> 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 <math>B</math> can guarantee? | Two players, <math>B</math> and <math>R</math>, play the following game on an infinite grid of unit squares, all initially colored white. The players take turns starting with <math>B</math>. On <math>B</math>'s turn, <math>B</math> selects one white unit square and colors it blue. On <math>R</math>'s turn, <math>R</math> selects two white unit squares and colors them red. The players alternate until <math>B</math> decides to end the game. At this point, <math>B</math> 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 <math>B</math> can guarantee? | ||
| − | (A simple polygon is a polygon (not necessarily convex) that does not intersect itself and has no holes) | + | (A simple polygon is a polygon (not necessarily convex) that does not intersect itself and has no holes.) |
==Solution== | ==Solution== | ||
Revision as of 12:53, 25 March 2023
Problem
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
