Maths Olympiad Prep

Library / /13 of 19

Combinatorics Difficulty 6.6 National olympiad Prove it Romania

Alina and Bogdan play a game on a 2×n2 \times n rectangular grid (n2n \ge 2) whose sides of length 22 are glued together to form a cylinder. Alternating moves, each player cuts out a unit square of the grid. A player loses if his/her move causes the grid to lose circular connection (two unit squares that only touch at a corner are considered to be disconnected). Suppose Alina makes the first move. Which player has a winning strategy?
Estonian Olympiad, 2009

Solution

If n=2j+1n = 2j + 1 is odd, Alina's strategy is the following: she cuts out a unit square and labels the columns from j-j to jj, the column from which the first unit square has been removed receiving the label 00. Starting at this point of the game, whenever Bogdan removes a square from column number k{j,,2,1,1,2,,j}k \in \{-j, \dots, -2, -1, 1, 2, \dots, j\}, Alina removes the unit square positioned in column number k-k and on the same row as the unit square removed by Bogdan in his last move. (If Bogdan removes the square remaining in column 00 he loses instantly.) If on Bogdan's move the cylinder didn't lose its circular connection, it will not lose it after Alina's move either. Hence, Alina will never destroy the cylinder and, as the game is bound to finish sooner or later, Bogdan is the one who will lose the game. Alina wins.

If n=2jn = 2j is even, Bogdan wins by adopting the following strategy: he labels the columns from j+1-j + 1 to jj, column 00 being the one from which Alina has removed a square in her initial move. Bogdan removes a square from column jj (the one lying opposite to column 00). From now on, if Alina removes a square from column number k{j+1,,2,1,1,2,,j1}k \in \{-j+1, \dots, -2, -1, 1, 2, \dots, j-1\}, Bogdan removes the square situated in the same row, but in the opposite column, namely k-k. (If Alina removes the remaining square from column 00 or from column jj, she loses instantly.) If Alina's move didn't dismantle the surface of the cylinder, Bogdan's move won't do it either. Eventually, Alina will dismantle the cylindrical surface and Bogdan will win.

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.