Let n and m be positive integers, n≥m. There is a game board of size 1×n divided into n unit squares and an unlimited supply of sticky tapes of size 1×m. On each move, any player adds a tape covering m 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 n and m are of equal parity then the first player can win regardless of how the opponent plays.
b) Is it true that, whenever n and m are of different parity, the second player can win regardless of how the first player plays?
Solution
Fig. 25
a) If n and m 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 n=11 and m=3). 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 n=5 and m=2, 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.
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.
