HMMT 二月 2005 · GEN2 赛 · 第 5 题

HMMT February 2005 — GEN2 Round — Problem 5

You and I play the following game on an 8 × 8 square grid of boxes: Initially, every box is empty. On your turn, you choose an empty box and draw an X in it; if any of the four adjacent boxes are empty, you mark them with an X as well. (Two boxes are adjacent if they share an edge.) We alternate turns, with you moving first, and whoever draws the last X wins. How many choices do you have for a first move that will enable you to guarantee a win no matter how I play?

解析

You and I play the following game on an 8 × 8 square grid of boxes: Initially, every box is empty. On your turn, you choose an empty box and draw an X in it; if any of the four adjacent boxes are empty, you mark them with an X as well. (Two boxes are adjacent if they share an edge.) We alternate turns, with you moving first, and whoever draws the last X wins. How many choices do you have for a first move that will enable you to guarantee a win no matter how I play? Solution: 0 I can follow a symmetry strategy: whenever you play in the box S , I play in the image ◦ of S under the 180 rotation about the center of the board. This ensures that the board will always be centrally symmetric at the beginning of your turn. Thus, if you play in ′ an empty box S , its symmetric image S is also empty at the beginning of your turn, and it remains so after your turn, since the even size of the board ensures that S can ′ be neither equal to nor adjacent to S . In particular, I always have a move available. Since the first person without an available move loses, you are guaranteed to lose. So the answer is that you have 0 choices for a first move that will guarantee your win.