We claim that the answer is all $\boxed{\alpha > 2}$. Call Poseidon "Po" and call Hephaestus "You, the engineer" (yes, you). We first show that you win when $\alpha > 2$. Define a round to be two turns, one by you and the one after by Po. Label the squares with coordinates and suppose that if Po flooded squares $F= \{(x,y)\}$, then $n$ is a positive integer such that $n \geq |x|+|y|$ for all $(x,y)\in F$ . Let $t_0\in \mathbb N$ such that \[ 2t_0+4n+3 \leq \alpha t_0. \]We claim that for the first $t_0-1$ turns, you can just build extend the levee so that it blocks the squares $(-n-1,y)$ from $(-n,y)$ for all $|y| < t$ (after the $t$th turn). It's clear that after $t$ rounds, the flood has spread to exactly $(x,y)$ with $|x|+|y| \leq n+t$ and $x \geq -n$. Therefore, on the $t_0$'th turn, Po will extend the levee so that there is a wall to the left of $(-n,y)$ for $|y| \leq n+t_0$ and one above $(x,n+t_0)$ and one below $(x,-n-t_0)$ for each of $-n\leq x\leq 0$. On the following $i$ turns, you just build a wall above $(i, n+t_0)$ and one below $(i, -n-t_0)$, extending the levee. Then, after the $t_0+i$th round, the flooded points $(x,y)$ are those satisfying $|y|\leq t_0+n$, $x \geq -n$, and $|x|+|y| \leq n+t_0+i$. In particular, this is contained in $R_i [-n,n+t_0+i]\times [-n-t_0, n+t_0]$. Continue this way until \[ 2(3t_0+4n+2+I)\leq \alpha(t_0+I), \]at which point on the $t_0+I$th turn we bound the entire rectangle $R_I$ and win. Next, we show that Po wins if $\alpha \leq 2$. We call a snorlax a simply connected animal. Let $R$ be a snorlax with perimeter $P$ and adjacency graph $G$. Note that since the lattice points can be two-colored and that walking around the perimeter with $P$ unit steps starts and ends at the same color, $P$ is even, say $P = 2k$. Lemma 1: If $R$ is a snorlax and $G$ does not have a bridge, and $AB$ are adjacent cells in $R$, and $C,D$ are next to $B$ perpendicular to $AB$, then one of $C,D$ is in $R$: \[ \begin{array}{c c c} & A & \\ C & B & D \\ & E & \end{array} \] Proof: Suppose by contradiction that neither $C$ nor $D$ is in $R$. Since $AB$ is not a bridge, $B$ must have some other neighbor in $R$ on the other side from $A$, say $E$. Then, we must have some other path from $A$ to $E$ that is not through $B$. In that case, the path either goes around $C$ around $D$. Whichever one it goes around must be in $R$ because $R$ is simply connected. $\Box$ Lemma 2: $\operatorname{diam} G\leq k-2$. Proof: We strong induce on $k$. If $k = 2$, then $R$ is a unit square and so $G$ is a single vertex. If $G$ is a bridge, then $R$ can be split into $R_1,R_2$ with perimeters $P_1, P_2$ and adjacency graphs $G_1,G_2$. Then, \[ \operatorname{diam} G \leq \operatorname{diam} G_1 + \operatorname{diam} G_2 + 1 \leq \frac{P_1}{2} - 2 + \frac{P_2}{2} - 2 + 1 = \frac{P+2}{2}-3 = k-2 \]indeed. Else, note that when we walk around the perimeter of $R$, we will have two consecutive 90 degree turns. Therefore, after suitable rotation, we have squares $S_1,\ldots, S_m$ so that [asy][asy] size(3cm); D((0,0)--(2,0)); D((0,1)--(2,1)); for(int i = 0; i <= 4; ++i) {D((i,0)--(i,1));} D((3,0)--(4,0)); D((3,1)--(4,1)); label("$S_1$",(0.5,0.5)); label("$S_2$",(1.5,0.5)); label("$\cdots$",(2.5,0.5)); label("$S_m$",(3.5,0.5)); label("$T_1$",(0.5,-0.5)); label("$T_2$",(1.5,-0.5)); label("$\cdots$",(2.5,-0.5)); label("$T_m$",(3.5,-0.5)); D((0,0)--(0,1)--(4,1)--(4,0),red); [/asy][/asy] where the red segments are part of the boundary of $R$. We claim now that the grid squares $T_1,\ldots, T_m$ are all in $R$. For $1\leq i \leq m-1$, $T_i\in R$ follows from Lemma $1$ since $S_i, S_{i+1}$ are both in $R$ but the square above $S_i$ is not. For $i = m$, note that $S_{m-1}, S_m$ are in $R$ but the square above $S_m$ is not. Thus, if $R'$ is $R$ with the $S_i$'s removed, then $R'$ is still a snorlax. Furthermore, $R'$'s perimeter is $2(k-1)$. Finally, if $R'$ has adjacency graph $G'$, then \[ \begin{aligned} \operatorname{diam} G &= \max\left(\operatorname{diam} G', m-1, \max_{\substack{v\in G' \\ 1\leq i \leq m}} d(v,S_i)\right) \\ &\leq \max\left(\operatorname{diam} G', m-1, \max_{\substack{v\in G' \\ 1\leq i \leq m}} d(v,T_i)+1\right) \\ &\leq \max\left(\operatorname{diam} G', m-1, \operatorname{diam}G' + 1\right) = \operatorname{diam}G' + 1 \end{aligned} \]where we note that $\operatorname{diam}G'\geq m-1$ since $d(T_1,T_m) = m-1$. Thus, \[ \operatorname{diam}G \leq \operatorname{diam}G' + 1 \leq k-3 + 1 = k-2, \]and the induction is complete. $\Box$ Now, suppose $\alpha = 2$ and Po just floods $O = (0,0)$ initially. Let $S_t$ be the set of squares flooded on the $t$th turn. Then, $d(O,A) = t$ (as vertices of $G$) for any $A\in S_t$. In particular, suppose you win on your $n$th turn. Then, the enclosed region $R$ has perimeter at most $2n$. Furthermore, \[ R\supset S_0\cup S_1\cup \cdots \cup S_{n-1}, \]and $S_{n-1}$ is nonempty. So, $\operatorname{diam} G \geq n-1$ since $d(O,A) = n-1$ for $A\in S_{n-1}$, while $R$'s perimeter is at most $2n$, contradicting Lemma 2. Thus, you cannot win in finitely many turns. $\blacksquare$

Here is a solution with eisirrational and Th3Numb3rThr33. The answer is $\alpha>2$. Proof of sufficiency. Take some $\alpha>2$. We show it is possible to contain the flood. Our strategy is as follows. Here the blue circle is a large region (that grows in both directions at a rate of $1$ cell per move) that contains all the flooded cells. [asy][asy] size(6cm); defaultpen(fontsize(10pt)); pen pri=black+linewidth(2); pen sec=black+linewidth(1); pen fil=royalblue; pair lbl=2*S; real r=1/2; pair A,B,C,D,O,del; del=(0,0); A=(0,0)+del; B=(0,4)+del; C=(6,4)+del; D=(6,0)+del; O=(A+C)/2; draw(A--B--C--D--cycle,pri); filldraw(circle(O,r),fil); draw( (A+(1,1))--(B+(1,-1)),sec); label("Step I: Build",D--A,lbl); del=(8,0); A=(0,0)+del; B=(0,4)+del; C=(6,4)+del; D=(6,0)+del; O=(A+C)/2; draw(A--B--C--D--cycle,pri); filldraw(circle(O,r),fil); draw( ( (A+D)/2+(r,1))--(A+(1,1))--(B+(1,-1))--( (B+C)/2+(r,-1)),sec); label("Step II: Engulf",D--A,lbl); del=(0,-6); A=(0,0)+del; B=(0,4)+del; C=(6,4)+del; D=(6,0)+del; O=(A+C)/2; draw(A--B--C--D--cycle,pri); filldraw(circle(O,r),fil); draw( (D+(-1,1))--(A+(1,1))--(B+(1,-1))--(C+(-1,-1)),sec); label("Step III: Zoom",D--A,lbl); del=(8,-6); A=(0,0)+del; B=(0,4)+del; C=(6,4)+del; D=(6,0)+del; O=(A+C)/2; draw(A--B--C--D--cycle,pri); filldraw(circle(O,r),fil); draw( (D+(-1,1))--(A+(1,1))--(B+(1,-1))--(C+(-1,-1))--cycle,sec); label("Step IV: Eat",D--A,lbl); [/asy][/asy] Build a giant wall. The total vertical height of the flood changes by at most $2$ a move. Start by building a wall sufficiently far away of arbitrary height. Since $\alpha>2$, the wall can be arbitrarily tall compared to the flood, while remaining a constant distance away from the center of the flood (since the wall can stop the flood from spreading to the other side). $~$ Engulf the flood. After the wall is sufficiently large, begin constructing walls rightward until the rightmost point on our walls is to the right of the rightmost point of the flood. The flood moves rightward at a rate of at most $1$ cell per move, while we can alternate between extending the top wall and the bottom wall, each increasing at a rate of $\alpha/2>1$ cells per move. If the original wall was large enough, the wall can extend past the flood without colliding into it, as the distance from the rightmost point of the wall and the rightmost point of the flood decreases by $\alpha/2-1$ cells each move. $~$ Zoom past the flood. Now, we essentially repeat the above process. The wall can be built rightward at a rate of $\alpha/2>1$, so we may extend an arbitrarily large distance past the rightmost point of the flood. $~$ Eat the flood. Finally, build the eastern wall. If we have ``zoomed'' sufficiently far past the flood, we can contain the entire flood, thus completing the process. Thus if $\alpha>2$, Hephaestus can stop the flood and save the world. Proof of lower bound. Given two cells $A$ and $B$ in the flood, let $L$ be the shortest path between $A$ and $B$ (including the endpoints) that does not intersect the levee, say it has length $|L|$, and furthermore say the levee has perimeter $P$. $~$ Claim. For any shortest path $L$ between two cells $A$ and $B$, we have $2(|L|+1)\le P$. Proof. From every cell in $L$, draw rays emanating from the center of that cell that do not lie along $L$; thus two rays are drawn from every cell except the endpoints, from which three are drawn. Stop these rays once they hit the levee (so that they are now segments), and call them beams. I claim that no point on the levee lies on two or more beams. Beams are either parallel or perpendicular, but perpendicular beams intersect at the center of a cell, and thus not on the levee, so for two beams to intersect on the levee, the lines containing them must coincide and the corresponding rays must be in the same direction. Let these two rays emanate from $X$ and $Y$. Then by definition of these beams, $L$ does not contain segment $XY$. But $\overline{XY}$ does not intersect the levee, so we may instead go directly from $X$ to $Y$, contradicting the assumption that $L$ is the shortest path. With this, the claim readily follows. $\blacksquare$ Suppose Poseidon starts with a flooded square $A$ surrounded by four flooded squares, and assume Hephaestus can stop the flood. Call the final state of the levee when the flood is sealed off the final levee. Let $B$ be a point in the contained flood, and let $L$ be the shortest path between $A$ and $B$ that does not intersect the final levee. Suppose that $|L|$ is maximal among all $B$ in the contained flood. Again let $P$ be the perimeter of the final levee. Note that if there is a wall at any point, it must be a part of the final levee. The flood will grow along $L$ until it reaches $B$. Since it already has a $1$ cell head-start (since $A$ is surrounded by four flooded squares) and we have assumed that $|L|$ is maximal, at most $|L|-1$ moves have passed. It follows that Hephaestus has built at most $\alpha(|L|-1)$ walls, so \[\alpha(|L|-1)\ge P\ge2(|L|+1)\implies\alpha>2,\]and we are done. @below thanks for pointing this out; I think it is fixed now

TheUltimate123 wrote: Note that it took at most $D$ moves for the flooded region to take its current shape. This is because at any point, the diameter of the flooded region increases by $1$, or is forever stuck. I don't think this is true. For instance if the flooded region is a 3x3 square and the levee is the perimeter of that square minus a wall not on a corner, and Poseidon takes his turn, the diameter is unchanged, but not stuck forever.

TheUltimate123 wrote: Here is a solution with eisirrational and Th3Numb3rThr33. Does this mean you discussed the test before December 16, noon Eastern time?

I'm sure they just worked it out in 41 minutes and edited in all the details later

TheUltimate123 wrote: [*]Engulf the flood. After the wall is sufficiently large, begin constructing walls rightward until the rightmost point on our walls is to the right of the rightmost point of the flood. The flood moves rightward at a rate of at most $1$ cell per move, while we can alternate between extending the top wall and the bottom wall, each increasing at a rate of $\alpha/2>1$ cells per move. If the original wall was large enough, the wall can extend past the flood without colliding into it, as the distance from the rightmost point of the wall and the rightmost point of the flood decreases by $\alpha/2-1$ cells each move. I think the rightmost point of the wall and the rightmost point of the flood decreases by $[\alpha/2]-1$ cells each move. So for $\alpha< 3 $ the quantity will 0. Here $[x]$ denote floor function.

OK, here is current draft of official solutions: We show that if $\alpha > 2$ then Hephaestus wins, but when $\alpha = 2$ (and hence $\alpha \le 2$) Hephaestus cannot contain even a single-cell flood initially. \bigskip Strategy for $\alpha > 2$: Impose ${\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)$ with $|x|+|y| \le d$ are flooded for some $d \ge 2$; thus on Hephaestus's $k$th turn, the water is contained in $|x|+|y| \le d+k-1$. Our goal is to contain the flood with a large rectangle. We pick large integers $N_1$ and $N_2$ such that \begin{align*} \alpha N_1 &> 2N_1 + (2d + 3) \\ \alpha (N_1+N_2) &> 2N_2 + (6N_1 + 8d + 4). \end{align*}Mark the points $X_i$, $Y_i$ as shown in the figure for $1 \le i \le 6$. The red figures indicate the distance between the marked points on the rectangle. [asy][asy] size(10cm); transform t = shift(-0.5,-0.5); path c(real x, real y) { return t * shift(x,y) * unitsquare ; } for (int x=-7; x<=7; ++x) { for (int y=-16; y<=2; ++y) { if (abs(x)+abs(y) <= 2) { filldraw(c(x,y), blue, grey); } else if (abs(x)+abs(y) <= 7) { filldraw(c(x,y), mediumcyan, grey); } else if (abs(x)+abs(y) <= 16) { filldraw(c(x,y), paleblue, grey); } else { filldraw(c(x,y), white, grey); } } } dotfactor *= 1.5; dot("$X_1$", (-0.5, 2.5), dir(115)); dot("$Y_1$", ( 0.5, 2.5), dir(65)); dot("$X_2$", (-5.5, 2.5), dir(90)); dot("$Y_2$", ( 5.5, 2.5), dir(90)); dot("$X_3$", (-7.5, 2.5), dir(135)); dot("$Y_3$", ( 7.5, 2.5), dir(45)); dot("$X_4$", (-7.5,-0.5), dir(180)); dot("$Y_4$", ( 7.5,-0.5), dir(0)); dot("$X_5$", (-7.5, -9.5), dir(180)); dot("$Y_5$", ( 7.5, -9.5), dir(0)); dot("$X_6$", (-7.5,-16.5), dir(180)); dot("$Y_6$", ( 7.5,-16.5), dir(0)); draw(box( (-7.5,-16.5), (7.5,2.5) ), black+1.4 ); label("$1$", (0, 2.5), dir(90), red); label("$N_1$", (-3, 2.5), dir(90), red); label("$N_1$", ( 3, 2.5), dir(90), red); label("$d$", (-6.5, 2.5), dir(90), red); label("$d$", ( 6.5, 2.5), dir(90), red); label("$d+1$", (-7.5, 1), dir(180), red); label("$d+1$", ( 7.5, 1), dir( 0), red); label("$N_2$", (-7.5, -5), dir(180), red); label("$N_2$", ( 7.5, -5), dir( 0), red); label("$N_1+d$", (-7.5, -13), dir(180), red); label("$N_1+d$", ( 7.5, -13), dir( 0), red); [/asy][/asy] We follow the following plan. Turn $1$: place wall $X_1 Y_1$. This cuts off the flood to the north. Turns $2$ through $N_1+1$: extend the levee to segment $X_2 Y_2$. This prevents further flooding to the north. Turn $N_1+2$: add in broken lines $X_4 X_3 X_2$ and $Y_4 Y_3 Y_2$ all at once. This cuts off the flood west and east. Turns $N_1+2$ to $N_1+N_2+1$: extend the levee along segments $X_4 X_5$ and $Y_4 Y_5$. This prevents further flooding west and east. Turn $N_1 + N_2 + 2$: add in the broken line $X_5 X_6 Y_6 Y_5$ all at once and win. \bigskip Proof for $\alpha = 2$: Suppose Hephaestus contains the flood on his $(n+1)$st turn. We prove that $\alpha > 2$ by showing that in fact at least $2n+4$ walls have been constructed. Let $c_0$, $c_1$, \dots, $c_n$ be a path of cells such that $c_0$ is the initial cell flooded, and in general $c_n$ is flooded on Poseidon's $n$th turn from $c_{n-1}$. The levee now forms a closed loop enclosing all $c_i$. Claim: If $c_i$ and $c_j$ are adjacent then $|i-j|=1$. Proof. Assume $c_i$ and $c_j$ are adjacent but $|i-j|>1$. Then the two cells must be separated by a wall. But the levee forms a closed loop, and now $c_i$ and $c_j$ are on opposite sides. $\blacksquare$ Thus the $c_i$ actually form a path. We color green any edge of the unit grid (wall or not) which is an edge of exactly one $c_i$ (i.e.\ the boundary of the polyomino). It is easy to see there are exactly $2n+4$ green edges. Now, from the center of each cell $c_i$, shine a laser towards each green edge of $c_i$ (hence a total of $2n+4$ lasers are emitted). An example below is shown for $n = 6$, with the levee marked in brown. [asy][asy]size(8cm); for (int i=0; i<=4; ++i) { for (int j=0; j<=4; ++j) { draw(shift(i,j)*unitsquare, lightgrey); } } draw( (0,0)--(0,2)--(2,2)--(2,3)--(0,3)--(0,5) --(5,5)--(5,2)--(3,2)--(3,0)--cycle, brown+1.5 ); filldraw( (0.1,1.1)--(2.9,1.1)--(2.9,4.9)--(1.1,4.9) --(1.1,4.1)--(2.1,4.1)--(2.1,1.9)--(0.1,1.9)--cycle, palecyan, green+1.5); label("$c_0$", (1.5,4.5)); label("$c_1$", (2.5,4.5)); label("$c_2$", (2.5,3.5)); label("$c_3$", (2.5,2.5)); label("$c_4$", (2.5,1.5)); label("$c_5$", (1.5,1.5)); label("$c_6$", (0.5,1.5)); draw( (0.5,1.5)--(0,1.5), red, EndArrow(TeXHead), Margin(2,1) ); draw( (0.5,1.5)--(0.5,2), red, EndArrow(TeXHead), Margin(2,1) ); draw( (0.5,1.5)--(0.5,0), red, EndArrow(TeXHead), Margin(2,1) ); draw( (1.5,1.5)--(1.5,2), red, EndArrow(TeXHead), Margin(2,1) ); draw( (1.5,1.5)--(1.5,0), red, EndArrow(TeXHead), Margin(2,1) ); draw( (2.5,1.5)--(3,1.5), red, EndArrow(TeXHead), Margin(2,1) ); draw( (2.5,1.5)--(2.5,0), red, EndArrow(TeXHead), Margin(2,1) ); draw( (2.5,2.5)--(2,2.5), red, EndArrow(TeXHead), Margin(2,1) ); draw( (2.5,2.5)--(5,2.5), red, EndArrow(TeXHead), Margin(2,1) ); draw( (2.5,3.5)--(0,3.5), red, EndArrow(TeXHead), Margin(2,1) ); draw( (2.5,3.5)--(5,3.5), red, EndArrow(TeXHead), Margin(2,1) ); draw( (2.5,4.5)--(2.5,5), red, EndArrow(TeXHead), Margin(2,1) ); draw( (2.5,4.5)--(5,4.5), red, EndArrow(TeXHead), Margin(2,1) ); draw( (1.5,4.5)--(1.5,5), red, EndArrow(TeXHead), Margin(2,1) ); draw( (1.5,4.5)--(0,4.5), red, EndArrow(TeXHead), Margin(2,1) ); draw( (1.5,4.5)--(1.5,3), red, EndArrow(TeXHead), Margin(2,1) ); [/asy][/asy] Claim: No wall is hit by more than one laser. Proof. Assume for contradiction that a wall $w$ is hit by lasers from $c_i$ and $c_j$. WLOG that laser is vertical, so $c_i$ and $c_j$ are in the same column (e.g.\ $(i,j) = (0,5)$ in figure). We consider two cases on the position of $w$. If $w$ is between $c_i$ and $c_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 $w$ lies above both $c_i$ and $c_j$ and assume WLOG $i < j$. Then we have found that there is no levee at all between $c_i$ and $c_j$. Let $\rho \ge 1$ be the distance between the centers of $c_i$ and $c_j$. Then $c_j$ is flooded in a straight line from $c_i$ within $\rho$ turns, and this is the unique shortest possible path. So this situation can only occur if $j = i+\rho$ and $c_i$, \dots, $c_j$ form a column. But then no vertical lasers from $c_i$ and $c_j$ may point in the same direction, contradiction. Since neither case is possible, the proof ends here. $\blacksquare$ This implies the levee has at least $2n+4$ walls (the number of lasers) on Hephaestus's $(n+1)$st turn. So $\alpha \ge \frac{2n+4}{n+1} > 2$. Remark: [Author comments] The author provides the following remarks. Even though the flood can be stopped when $\alpha = 2 + \varepsilon$, it takes a very long time to do that. Starting from a single flooded cell, the strategy I have outlined requires $\Theta(1 / \varepsilon^2)$ days. Starting from several flooded cells contained within an area of diameter $D$, it takes $\Theta( D / \varepsilon^2)$ days. I do not know any strategies that require fewer days than that. There is a gaping chasm between $\alpha \le 2$ and $\alpha > 2$. Since $\alpha \le 2$ does not suffice even when only one cell is flooded in the beginning, there are in fact no initial configurations at all for which it is sufficient. On the other hand, $\alpha > 2$ works for all initial configurations. The second half of the solution essentially estimates the perimeter of a polyomino in terms of its diameter (where diameter is measured entirely within the polyomino). It appears that this has not been done before, or at least I was unable to find any reference for it. I did find tons of references where the perimeter of a polyomino is estimated in terms of its area, but nothing concerning the diameter. My argument is a formalisation of the intuition that if $P$ is any shortest path within some weirdly-shaped polyomino, then the boundary of that polyomino must hug $P$ rather closely so that $P$ cannot be shortened.

v_Enhance wrote: OK, here is current draft of official solution: By the way, can you tell me where I can find the official solutions(USA TST)? Thanks

The solutions are posted on https://web.evanchen.cc/problems.html now. Evan

We claim that $\alpha$ works iff $\alpha>2$. Part 1: $\alpha=2$ fails (implying $\alpha \leq 2$ also fails). We claim that $\alpha = 2$ fails if there is a single flooded cell. Indeed, let the square with the initial flooded cell be $C_I$. Suppose that Hephaestus wins. Let $F$ denote the chessboard polygon defined by this loop. Let the cell $C_F$ be one of the last cells to be flooded. Notice that there is the minimal chain of adjacent cells $C_0,C_1,...,C_k$ where $C_0=C_I$, $C_k=C_F$, and $C_i$ has taxicab distance $i$ to $C$ assuming the taxicab never leaves $F$. Thus, $C_F$ will be flooded after exactly $k$ moves. Claim 1: If $S$ denotes the chessboard polygon formed by the cells in $C_0, C_1,..., C_k$ then the perimeter of $S$ is less than or equal to the perimeter of $F$. Indeed, assume that the perimeter of $S$ is greater than $F$. This means the number of unit edges in $S$ exceeds the number in $F$. Thus, there are a pair of edges in $S$ which face the same edge of $F$ by pigeonhole principle. Since an edge in $C_i$ and $C_j$ are facing in the same direction and hitting the same edge, then it is known that $C_i$ and $C_j$ are not connected by a straight line of squares. But, one can clearly connect $C_i$ and $C_j$ with a straight line of cells without leaving $F$ because if we left $F$, the two edges of $S$ would not be facing the same edge of $F$. But, the shortest path to any two squares on the same row or column is clearly a straight line. Thus, we know a straight line of squares connecting $C_i$ and $C_j$ exists, does not leave $F$, and is strictly shorter than our current path. This contradicts minimality. $\square$ Claim 2: $S$ has perimeter of at least $2k+4$ Indeed, notice that $C_I$ and $C_F$ have three exposed edges and all intermediate $C_i$'s have 2 exposed edges. This gives at least $2(k-1)+6=2k+4$ edges. Notice that we are not overcounting since if cells $C_i$ and $C_j$ share an edge then this will contradict the result found in claim 1. Namely, no edges of $S$ cells can be facing the same edge of $F$. $\square$ Notice that $C_k$ fills after exactly $k$ moves by construction. Thus, $F$ has perimeter $2k$ and $S$ has perimeter $2k+4$ which contradicts claim 1. $\square$ Part 2: $\alpha > 2$ always works. Fix an arbitrary cartesian plane with axis's parallel to the gridlines Step 1: Build wall Assume wlog that the flood is longer than it is tall. Build a wall parallel to the $x$-axis under the flood in such a way that the leftmost wall is on the same column as the leftmost flooded square. Continue to build this wall until it is sufficiently close to being partitioned into segments of length $L$ and $(\alpha-1)L$ where $L$ is the length of the flood. Step 2: Block Two Sides Continue to extend the leftmost side of the levee to keep it in step with the leftmost flooded cell. Meanwhile, start extending the right end of the levee up. We claim that doing this will make the levee taller than the flood for sufficiently large $L$. Indeed, the disturbances in the original flood get arbitrarily small as the left side of the flood approaches a line $45^{\circ}$ of the x-axis. Thus, will meet the right wall at a rate approaching $1$ while the wall builds at a rate of $\alpha-1>1$. Thus, the levee will exceed the height of the flood. Step 3: Block Three Sides Continue to extend the horizontal part of the levee by 1 each turn and the verticle part of the levee by the rest of the walls given in that turn. As we extend arbitrarily far, the disturbances in the original flood get arbitrarily small as the left side of the flood approaches a line $45^{\circ}$ of the x-axis. Once the disturbances are sufficiently small, start building from the topmost point in the levee horizontally. You will be building at a speed of $\alpha-1$ while the flood reaches the top of the levee at a speed arbitrarily close to $1$. Since $\alpha-1>1$, you will outrun the flood. Step 4: Extend Once the two endpoints of the levee are on the same line parallel to the $y$-axis, start building each end of the levee at an equal pace. You will continue to outrun the levee since $\alpha/2 > 1$. Extend these until they are arbitrarily long. Notice that the length of the levee over the length of the flood approaches a constant. Step 5: Victory Since the height is now a constant, it will get arbitrarily small compared to the length. Thus, one can close the two ends without risking a spill. This contains the flood. $\blacksquare$

blackbluecar wrote: Clearly, the convex hull of $F$ is both more efficient and a valid loop. It's not that simple, as there might be a moment $n'$ where you need more than $\alpha n'$ walls - it's not just about the final state. You're basically assuming that the water would spread the same if the loop were to be made convex, but this is not true as there is nothing to stop it inside of the convex hull, so it's likely going to fill up more quickly.

a1267ab wrote: Let $\alpha \geq 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 $\alpha n$ after his $n$th 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? *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 Hephaestus cannot add more walls. Since each wall has length $\mbox{\footnotesize \(1\)}$, the length of the levee is $\mbox{\footnotesize \(k\)}$. Nikolai Beluhov

There's a hidden observation that is pretty important (you may figure it out when you try to show $\alpha=2$ is not enough): Instead of construct a strategy for Hephaestus, we assume that Hepharstus has a strategy and look at the final moment. This strategy work only if a leeve is built before the adjacent grid is flooded. This observation may be trivial but quite useful to understand and work out the details for this problem.

$\alpha > 2$ Wait until it's a diamond, then draw a line from top tip to top left portion to left tip, and continuously extend the top bit right and left bit down. Once you've gained enough walls, extend the left wall to the bottom left then to the bottom tip, the top wall to the top right then to the right tip, then extend the bottom part right, the right part down, and finish the box at the bottom right corner. The flood is contained. $\alpha = 2$ Consider the strategy minimizing the number of walls utilized first and maximizing the surrounded area second. Travel along the wall, WLOG the flood is to the left, then locally looking at right turns with casework shows none can exist, hence the wall must be a rectangle, say with width $w$ and height $h$. Now this rectangle will be entirely filled by the flood on turn $w+h-1$, but it requires $2w+2h$ walls to maintain, so we will be one short and during Poseidon's turn his flood will escape the rectangle, so we lose. Hence answer is $\alpha > 2$.

Why doesn't Hephaestus, the biggest god, simply eat Poseidon? Unconvincingly sus global arguement. Claim: This is possible if $\alpha \ge 2$. Proof. Hephaestus chooses a wall $N$ away from the leftmost flooded cell, such that he can create a wall of $\alpha N$ thats at least $2N$ larger than the initial height. By further expanding this law, Hephaestus fully bounds the wall. with growth rate $\frac{\alpha}{2}$ on each wall. Hephaestus keeps expanding this wall until its sufficiently long such that Poseidon can turn the flooded cells into a bounding pyramid fully contained by the wall. This is possible since the wall grows in each direction faster. At this point, Hephaestus expands the wall to the right as top walls and bottom walls with growth rate $\frac{\alpha}{2}$. This inductively prevents flooded cells from passing. He repeats this until the distance between is arbitrarily large, at which point he finishes the fourth wall. $\blacksquare$ Claim: This is impossible if $\alpha \le 2$. Proof. Poseidon places a single cell. We generalize to the case where the path can self-intersect. FTSOC suppose that Hephaestus can win by creating a path $C$. Suppose that the path is concave once at a cell. I claim that we can reorder the path to get rid of this concave corner. Note that if the newly uncovered square gets filled in after its two neighbors, the result follows immediately. Else, the flooding must go from one neighbor to this new cell to the other neighbor. However, since the path is nonintersecting, it follows that this also held for the original levee path. Repeat this process until all such corners are gone. The case for the path containing two concave corners at once is similar, as reordering the path can only additionally flood one cell. Thus, we can WLOG that $C$ is a rectangle. This immediately gives a contradiction as it is impossible for Hephaestus to place a levee in all four directions from the starting flood position that quickly. $\blacksquare$