Browse · MathNet
PrintTHE 68th NMO SELECTION TESTS FOR THE JUNIOR BALKAN MATHEMATICAL OLYMPIAD
Romania counting and probability
Problem
Alina and Bogdan play a game on a rectangular grid () whose sides of length 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 is odd, Alina's strategy is the following: she cuts out a unit square and labels the columns from to , the column from which the first unit square has been removed receiving the label . Starting at this point of the game, whenever Bogdan removes a square from column number , Alina removes the unit square positioned in column number and on the same row as the unit square removed by Bogdan in his last move. (If Bogdan removes the square remaining in column 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 is even, Bogdan wins by adopting the following strategy: he labels the columns from to , column being the one from which Alina has removed a square in her initial move. Bogdan removes a square from column (the one lying opposite to column ). From now on, if Alina removes a square from column number , Bogdan removes the square situated in the same row, but in the opposite column, namely . (If Alina removes the remaining square from column or from column , 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.
If is even, Bogdan wins by adopting the following strategy: he labels the columns from to , column being the one from which Alina has removed a square in her initial move. Bogdan removes a square from column (the one lying opposite to column ). From now on, if Alina removes a square from column number , Bogdan removes the square situated in the same row, but in the opposite column, namely . (If Alina removes the remaining square from column or from column , 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.
Final answer
Alina wins when the number of columns is odd; Bogdan wins when the number of columns is even.
Techniques
Games / greedy algorithmsInvariants / monovariants