Maths Olympiad Prep

Library / /322 of 377

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

You and I play the following game on an 8×88 \times 8 square grid of boxes: Initially, every box is empty. On your turn, you choose an empty box and draw an XX in it; if any of the four adjacent boxes are empty, you mark them with an XX as well. (Two boxes are adjacent if they share an edge.) We alternate turns, with you moving first, and whoever draws the last XX 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 SS, I play in the image of SS under the 180180^{\circ} 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 SS, its symmetric image SS^{\prime} 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 SS can be neither equal to nor adjacent to SS^{\prime}. 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.