HMMT 十一月 2015 · THM 赛 · 第 4 题
HMMT November 2015 — THM Round — Problem 4
题目详情
- Consider a 4 × 4 grid of squares. Aziraphale and Crowley play a game on this grid, alternating turns, with Aziraphale going first. On Aziraphales turn, he may color any uncolored square red, and on Crowleys turn, he may color any uncolored square blue. The game ends when all the squares are colored, and Aziraphales 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 Aziraphales score be?
解析
- Consider a 4 × 4 grid of squares. Aziraphale and Crowley play a game on this grid, alternating turns, with Aziraphale going first. On Aziraphales turn, he may color any uncolored square red, and on Crowleys turn, he may color any uncolored square blue. The game ends when all the squares are colored, and Aziraphales 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 Aziraphales score be? Proposed by: Alexander Katz Answer: 6 We claim that the answer is 6. On Aziraphale’s first two turns, it is always possible for him to take 2 adjacent squares from the central four; without loss of generality, suppose they are the squares at (1 , 1) and (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 6. 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). If Aziraphale is also allowed to take (1 , 0), he will clearly attain at least 6 adjacent red squares as each red square in this row has two adjacent squares to it, and otherwise (if Crowley takes 4 (1 , 0)), Aziraphale will take (0 , 1) and guarantee a score of at least 4 + = 6 as there are 4 uncolored 2 squares adjacent to a red one. Therefore, the end score will be at least 6. We now show that this is the best possible for Aziraphale; i.e. Crowley can always limit the score to 6. 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 4 will occur entirely in one half of the grid, but then the maximum score is 4 + = 6. 2 The optimal score is thus both at least 6 and at most 6, so it must be 6 as desired.