CombinatoricsDifficulty 5.6AIME, harderProve itUnited States
Problem:
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
Solution:
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.
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.