Maths Olympiad Prep

Library / /98 of 101

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it Estonia

Juku and Miku play the following game on a grid of dimensions n×mn \times m: In the beginning, all unit squares are white. Each player on their turn paints one white unit square either red or blue of their choice, but no two unit squares with a common side or a common vertex can be painted the same color. The players take turns and Juku starts. A player who cannot make the allowed move has lost. Is it possible for Juku to win the game regardless of how Miku plays if:

a) n=2023n = 2023 and m=2023m = 2023;

b) n=2023n = 2023 and m=2024m = 2024;

c) n=2024n = 2024 and m=2024m = 2024?

Solution

If nn and mm are even, then there is a middle square on the grid. Let Juku paint the middle square any color on the first move. From now on, each of Juku's moves should mirror Miku's last move relative to the center of the grid. If before Miku's move the position is symmetrical with respect to the center of the grid, then Juku can certainly respond symmetrically, and before Miku's next move the position is again symmetrical with respect to the center of the grid. Therefore Juku always wins.

If nn or mm is even, then Miku can mirror Juku's last move with respect to the center of the grid in each of his moves, but with the opposite color. Then, before each move by Juku the unit squares symmetrical to the center are of the opposite color. So if Juku can make a move, Miku can respond symmetrically to the center. Consequently with this strategy Miku wins. It follows that on 2023×20232023 \times 2023 grid Juku can win for any moves of Miku, on 2023×20242023 \times 2024 and 2024×20242024 \times 2024 grids it is not always possible.

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 and solution reproduced as published; topic and difficulty added by this site.