Problem

Source: USA TST for EGMO 2020, Problem 1 (adapted from IMO TST Problem 3)

Tags: combinatorics



Vulcan and Neptune play a turn-based game on an infinite grid of unit squares. Before the game starts, Neptune chooses a finite number of cells to be flooded. Vulcan is building a levee, which is a subset of unit edges of the grid (called walls) forming a connected, non-self-intersecting path or loop*. The game then begins with Vulcan moving first. On each of Vulcan’s turns, he may add up to three new walls to the levee (maintaining the conditions for the levee). On each of Neptune’s turns, every cell which is adjacent to an already flooded cell and with no wall between them becomes flooded as well. Prove that Vulcan can always, in a finite number of turns, build the levee into a closed loop such that all flooded cells are contained in the interior of the loop, regardless of which cells Neptune initially floods. *More formally, there must exist lattice points $\mbox{\footnotesize \(A_0, A_1, \dotsc, A_k\)}$, pairwise distinct except possibly $\mbox{\footnotesize \(A_0 = A_k\)}$, such that the set of walls is exactly $\mbox{\footnotesize \(\{A_0A_1, A_1A_2, \dotsc , A_{k-1}A_k\}\)}$. Once a wall is built it cannot be destroyed; in particular, if the levee is a closed loop (i.e. $\mbox{\footnotesize \(A_0 = A_k\)}$) then Vulcan cannot add more walls. Since each wall has length $\mbox{\footnotesize \(1\)}$, the length of the levee is $\mbox{\footnotesize \(k\)}$.