Maths Olympiad Prep

Library / /726 of 740

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:

Consider a 4×44 \times 4 grid of squares. Aziraphale and Crowley play a game on this grid, alternating turns, with Aziraphale going first. On Aziraphale's turn, he may color any uncolored square red, and on Crowley's turn, he may color any uncolored square blue. The game ends when all the squares are colored, and Aziraphale's score is the area of the largest closed region that is entirely red. If Aziraphale wishes to maximize his score, Crowley wishes to minimize it, and both players play optimally, what will Aziraphale's score be?

Solution

Solution:

We claim that the answer is 66.

On Aziraphale's first two turns, it is always possible for him to take 22 adjacent squares from the central four; without loss of generality, suppose they are the squares at (1,1)(1,1) and (1,2)(1,2). If allowed, Aziraphale's next turn will be to take one of the remaining squares in the center, at which point there will be seven squares adjacent to a red square, and so Aziraphale can guarantee at least two more adjacent red squares. After that, since the number of blue squares is always at most the number of red squares, Aziraphale can guarantee another adjacent red square, making his score at least 66.

If, however, Crowley does not allow Aziraphale to attain another central red square—i.e., coloring the other two central squares blue—then Aziraphale will continue to take squares from the second row, WLOG (1,3)(1,3). If Aziraphale is also allowed to take (1,0)(1,0), he will clearly attain at least 66 adjacent red squares as each red square in this row has two adjacent squares to it, and otherwise (if Crowley takes (1,0)(1,0)), Aziraphale will take (0,1)(0,1) and guarantee a score of at least 4+42=64+\frac{4}{2}=6 as there are 44 uncolored squares adjacent to a red one.

Therefore, the end score will be at least 66. We now show that this is the best possible for Aziraphale; i.e., Crowley can always limit the score to 66. Crowley can play by the following strategy: if Aziraphale colors a square in the second row, Crowley will color the square below it; if Aziraphale colors a square in the third row, Crowley will color the square above it. Otherwise, if Aziraphale colors a square in the first or fourth rows, Crowley will color an arbitrary square in the same row. It is clear that the two "halves" of the board cannot be connected by red squares, and so the largest contiguous red region will occur entirely in one half of the grid, but then the maximum score is 4+42=64+\frac{4}{2}=6.

The optimal score is thus both at least 66 and at most 66, so it must be 66 as desired.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.