Browse · MathNet
PrintEstonian Mathematical Olympiad
Estonia counting and probability
Problem
Let and be positive integers, . There is a game board of size divided into unit squares and an unlimited supply of sticky tapes of size . On each move, any player adds a tape covering consecutive unit squares on the board precisely, at least one of which is not yet covered by any tape. Two players move alternately and the one who can make no move loses.
a) Prove that if and are of equal parity then the first player can win regardless of how the opponent plays.
b) Is it true that, whenever and are of different parity, the second player can win regardless of how the first player plays?
a) Prove that if and are of equal parity then the first player can win regardless of how the opponent plays.
b) Is it true that, whenever and are of different parity, the second player can win regardless of how the first player plays?
Solution
Fig. 25
a) If and are of equal parity, then the first player to move can cover the central squares in such a way that an equal number of uncovered squares remain on both sides (Fig. 25 with and ). The first player can now respond to each of the opposing player's moves by a symmetric move that ensures that uncovered squares remain symmetric w.r.t. the centre of the board after their move. Indeed, the starting move ensures that any subsequent move can cover uncovered squares only to one side of the centre and the first player is free to make symmetric moves in response to the second player. The number of uncovered squares decreases on each move; thus, the second player will lose.
Fig. 26
b) If and , then the first player can cover two squares at the edge of the board on their first move (Fig. 26). Any move by the second player will now leave either 1 or 2 consecutive squares uncovered, and the first player can cover those on their next move, ensuring victory.
Answer: b) No.
a) If and are of equal parity, then the first player to move can cover the central squares in such a way that an equal number of uncovered squares remain on both sides (Fig. 25 with and ). The first player can now respond to each of the opposing player's moves by a symmetric move that ensures that uncovered squares remain symmetric w.r.t. the centre of the board after their move. Indeed, the starting move ensures that any subsequent move can cover uncovered squares only to one side of the centre and the first player is free to make symmetric moves in response to the second player. The number of uncovered squares decreases on each move; thus, the second player will lose.
Fig. 26
b) If and , then the first player can cover two squares at the edge of the board on their first move (Fig. 26). Any move by the second player will now leave either 1 or 2 consecutive squares uncovered, and the first player can cover those on their next move, ensuring victory.
Answer: b) No.
Final answer
b) No
Techniques
Invariants / monovariantsGames / greedy algorithms