Track / Stage 7 / 11 of 300 #1411 of 1964

Problem 1411

National olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.0 Prove it

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$}$ .

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

To prove that Vulcan can always build a levee that encloses all initially flooded cells, we will use a strategy that involves constructing a levee in a systematic manner. We will show that Vulcan can always build the levee into a closed loop such that all flooded cells are contained within the loop, regardless of the initial configuration of flooded cells chosen by Neptune.

1. Initial Setup:
- Let $s$ be the side length of the smallest square that contains all initially flooded cells.
- We will assume that all cells within this square are initially flooded, as removing some initially flooded cells does not make the problem harder for Vulcan.

2. Step 1: Construct the Top-Right Corner:
- In the first $2s$ turns, Vulcan will build the top-right corner of the levee.
- He will construct the top and right walls such that they are $2s$ units away from the top and right sides of the square.
- This ensures that the flood boundary does not reach the levee until after $2s$ turns.

$\text{Top wall: } (0, 0) \rightarrow (2s, 0) \\ \text{Right wall: } (2s, 0) \rightarrow (2s, 2s)$

3. Step 2: Extend the Top and Right Walls:
- In the next $5s$ turns, Vulcan will extend the top wall to $7s$ units and the right wall downward by $5s$ units.
- This ensures that the flood boundary just reaches the left side of the levee after $7s$ turns in total.

$\text{Top wall: } (2s, 0) \rightarrow (7s, 0) \\ \text{Right wall: } (2s, 2s) \rightarrow (2s, 7s)$

4. Step 3: Extend the Left and Right Walls:
- In the next $5s$ turns, Vulcan will build two walls on the left side of the levee and one wall on the right side.
- This ensures that the left and right walls are equal in length.

$\text{Left wall: } (0, 0) \rightarrow (0, 5s) \\ \text{Right wall: } (2s, 7s) \rightarrow (2s, 12s)$

5. Step 4: Complete the Levee:
- In the final $14s$ turns, Vulcan will increase the length downward of one of the left or right walls by 1 unit and the other by 2 units.
- Once the total length of the left or right wall reaches $29s$ , Vulcan will begin constructing the bottom wall of the levee.
- After these $14s$ moves (and $26s$ moves in total), the bottom edge of the flood boundary just hits the bottom of the levee.

$\text{Left wall: } (0, 5s) \rightarrow (0, 29s) \\ \text{Right wall: } (2s, 12s) \rightarrow (2s, 29s) \\ \text{Bottom wall: } (0, 29s) \rightarrow (2s, 29s)$

By following this strategy, Vulcan can always build a levee that encloses all initially flooded cells, regardless of the initial configuration chosen by Neptune. The levee will form a closed loop, ensuring that all flooded cells are contained within the interior of the loop.

$\blacksquare$

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.