Maths Olympiad Prep

Track / Stage 6 / 316 of 400 #1316 of 1964

Problem 1316

National olympiad, first round
Combinatorics Difficulty 6.6 Prove it THE 68th NMO SELECTION TESTS FOR THE JUNIOR BALKAN MATHEMATICAL OLYMPIAD · 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

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.