Maths Olympiad Prep

Library / /10 of 11

Combinatorics Difficulty 9.0 IMO level Prove it United States

Let α1\alpha \ge 1 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 αn\alpha n 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 α\alpha 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 α>2\alpha > 2 then Hephaestus wins, but when α=2\alpha = 2 (and hence α2\alpha \le 2) Hephaestus cannot contain even a single-cell flood initially.

Strategy for α>2\alpha > 2: Impose Z2\mathbb{Z}^2 coordinates on the cells. Adding more flooded cells does not make our task easier, so let us assume that initially the cells (x,y)(x, y) with x+yd|x| + |y| \le d are flooded for some d2d \ge 2; thus on Hephaestus's kkth turn, the water is contained in x+yd+k1|x| + |y| \le d + k - 1. Our goal is to contain the flood with a large rectangle.
We pick large integers N1N_1 and N2N_2 such that
αN1>2N1+(2d+3)α(N1+N2)>2N2+(6N1+8d+4). \alpha N_1 > 2N_1 + (2d + 3) \\ \alpha(N_1 + N_2) > 2N_2 + (6N_1 + 8d + 4).
Mark the points XiX_i, YiY_i as shown in the figure for 1i61 \le i \le 6. The red figures indicate the distance between the marked points on the rectangle.
Figure 1

We follow the following plan.
* Turn 1: place wall X1Y1X_1Y_1. This cuts off the flood to the north.
* Turns 2 through N1+1N_1 + 1: extend the levee to segment X2Y2X_2Y_2. This prevents further flooding to the north.
* Turn N1+2N_1 + 2: add in broken lines X4X3X2X_4X_3X_2 and Y4Y3Y2Y_4Y_3Y_2 all at once. This cuts off the flood west and east.
* Turns N1+2N_1 + 2 to N1+N2+1N_1 + N_2 + 1: extend the levee along segments X4X5X_4X_5 and Y4Y5Y_4Y_5. This prevents further flooding west and east.
* Turn N1+N2+2N_1 + N_2 + 2: add in the broken line X5X6Y6Y5X_5X_6Y_6Y_5 all at once and win.

Proof for α=2\alpha = 2: Suppose Hephaestus contains the flood on his (n+1)(n+1)st turn. We prove that α>2\alpha > 2 by showing that in fact at least 2n+42n + 4 walls have been constructed.
Let c0,c1,,cnc_0, c_1, \dots, c_n be a path of cells such that c0c_0 is the initial cell flooded, and in general cnc_n is flooded on Poseidon's nnth turn from cn1c_{n-1}. The levee now forms a closed loop enclosing all cic_i.

Claim — If cic_i and cjc_j are adjacent then ij=1|i - j| = 1.
Proof. Assume cic_i and cjc_j are adjacent but ij>1|i - j| > 1. Then the two cells must be separated by a wall. But the levee forms a closed loop, and now cic_i and cjc_j are on opposite sides. \square

Thus the cic_i actually form a path. We color green any edge of the unit grid (wall or not) which is an edge of exactly one cic_i (i.e. the boundary of the polyomino). It is easy to see there are exactly 2n+42n + 4 green edges.

Now, from the center of each cell cic_i, shine a laser towards each green edge of cic_i (hence a total of 2n+42n + 4 lasers are emitted). An example below is shown for n=6n = 6, with the levee marked in brown.
Figure 2

Claim — No wall is hit by more than one laser.
Proof. Assume for contradiction that a wall ww is hit by lasers from cic_i and cjc_j. WLOG that laser is vertical, so cic_i and cjc_j are in the same column (e.g. (i,j)=(0,5)(i, j) = (0, 5) in figure). We consider two cases on the position of ww.
* If ww is between cic_i and cjc_j, 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 ww lies above both cic_i and cjc_j and assume WLOG i<ji < j. Then we have found that there is no levee at all between cic_i and cjc_j.
Let ρ1\rho \ge 1 be the distance between the centers of cic_i and cjc_j. Then cjc_j is flooded in a straight line from cic_i within ρ\rho turns, and this is the unique shortest possible path. So this situation can only occur if j=i+ρj = i + \rho and ci,,cjc_i, \dots, c_j form a column. But then no vertical lasers from cic_i and cjc_j may point in the same direction, contradiction.

Since neither case is possible, the proof ends here. \Box

This implies the levee has at least 2n+42n + 4 walls (the number of lasers) on Hephaestus's (n+1)(n+1)st turn. So α2n+4n+1>2\alpha \ge \frac{2n+4}{n+1} > 2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.