CombinatoricsDifficulty 5.5AIME, harderProve itUnited States
Problem:
Two players, Cat and Mouse, play the following game on a 4×4 checkerboard. Each player places a checker on a cell of the board (Cat goes first). Then, the two players take turns moving their checkers to an adjacent square, either vertically or horizontally (Cat again goes first). If, after either player's move, the two checkers occupy the same square, Cat wins. Otherwise, if each checker has made 2013 moves without this happening, Mouse wins. Determine, with proof, which player has a winning strategy.
Solution
Solution:
Mouse has a winning strategy. Color the cells of the checkerboard black and white alternately, in standard checkerboard fashion, so that adjacent cells are opposite colors. Whichever color Cat places his checker on, Mouse places his checker on a different cell of the same color. Then each time Cat moves, the checkers will be on opposite colors, and each time Mouse moves, the checkers will be on the same color. So Cat can never land on Mouse; it remains for Mouse to avoid landing on Cat. Since each cell has at least two neighbors, this is easy to do.
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.