Let be a real number. Hephaestus and Poseidon play a turn-based game on an infinite grid of unit squares. Before the game starts, Poseidon chooses a finite number of cells to be flooded. Hephaestus 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 Hephaestus moving first. On each of Hephaestus's turns, he adds one or more walls to the levee, as long as the total length of the levee is at most after his nth turn. On each of Poseidon's turns, every cell which is adjacent to an already flooded cell and with no wall between them becomes flooded as well.
Hephaestus wins if the levee forms a closed loop such that all flooded cells are contained in the interior of the loop — hence stopping the flood and saving the world. For which can Hephaestus guarantee victory in a finite number of turns no matter how Poseidon chooses the initial cells to flood?
Solution
We show that if then Hephaestus wins, but when (and hence ) Hephaestus cannot contain even a single-cell flood initially.
Strategy for : Impose coordinates on the cells. Adding more flooded cells does not make our task easier, so let us assume that initially the cells with are flooded for some ; thus on Hephaestus's th turn, the water is contained in . Our goal is to contain the flood with a large rectangle.
We pick large integers and such that
Mark the points , as shown in the figure for . The red figures indicate the distance between the marked points on the rectangle.
We follow the following plan.
* Turn 1: place wall . This cuts off the flood to the north.
* Turns 2 through : extend the levee to segment . This prevents further flooding to the north.
* Turn : add in broken lines and all at once. This cuts off the flood west and east.
* Turns to : extend the levee along segments and . This prevents further flooding west and east.
* Turn : add in the broken line all at once and win.
Proof for : Suppose Hephaestus contains the flood on his st turn. We prove that by showing that in fact at least walls have been constructed.
Let be a path of cells such that is the initial cell flooded, and in general is flooded on Poseidon's th turn from . The levee now forms a closed loop enclosing all .
Claim — If and are adjacent then .
Proof. Assume and are adjacent but . Then the two cells must be separated by a wall. But the levee forms a closed loop, and now and are on opposite sides.
Thus the actually form a path. We color green any edge of the unit grid (wall or not) which is an edge of exactly one (i.e. the boundary of the polyomino). It is easy to see there are exactly green edges.
Now, from the center of each cell , shine a laser towards each green edge of (hence a total of lasers are emitted). An example below is shown for , with the levee marked in brown.
Claim — No wall is hit by more than one laser.
Proof. Assume for contradiction that a wall is hit by lasers from and . WLOG that laser is vertical, so and are in the same column (e.g. in figure). We consider two cases on the position of .
* If is between and , then we have found a segment intersecting the levee exactly once. But the endpoints of the segment lie inside the levee. This contradicts the assumption that the levee is a closed loop.
* Suppose lies above both and and assume WLOG . Then we have found that there is no levee at all between and .
Let be the distance between the centers of and . Then is flooded in a straight line from within turns, and this is the unique shortest possible path. So this situation can only occur if and form a column. But then no vertical lasers from and may point in the same direction, contradiction.
Since neither case is possible, the proof ends here.
This implies the levee has at least walls (the number of lasers) on Hephaestus's st turn. So .