Browse · MathNet
PrintEstonian Mathematical Olympiad
Estonia counting and probability
Problem
Juku and Miku play the following game on a grid of dimensions : 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) and ;
b) and ;
c) and ?
a) and ;
b) and ;
c) and ?
Solution
If and 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 or 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 grid Juku can win for any moves of Miku, on and grids it is not always possible.
If or 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 grid Juku can win for any moves of Miku, on and grids it is not always possible.
Final answer
a) Yes; b) No; c) No
Techniques
Games / greedy algorithmsColoring schemes, extremal arguments