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\)}$.
Problem
Source: USA TST for EGMO 2020, Problem 1 (adapted from IMO TST Problem 3)
Tags: combinatorics
v_Enhance
16.12.2019 20:51
Just to cross-reference, this is the $\alpha=3$ case of the IMO TST #3 (with greek gods replaced by roman equivalents).
alifenix-
16.12.2019 21:44
I really hated this problem, it took me 2.5 hours to do -_-
Observe that at any point, you can add flooded cells because it is a disadvantage to Vulcan.
Show that you can seal off one side of a $1$-by-$n$ rectangle, using only two levees per move, in some number of moves.
Start by sealing off a corner using 2 moves on the first move. Then hold one side "at bay" while using ^^ to slowly conquer the entire flooded area, one side at a time.
Start with:
[asy][asy]
draw((0,0)--(3,0)--(3,1)--(0,1)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1));
draw((3,0)--(3,1), linewidth(2)+red);
[/asy][/asy]
End with (+2 (alternating shades blue) levees on this side per move):
[asy][asy]
pen lb = linewidth(2)+rgb(0,130,255);
pen b = linewidth(2)+blue;
fill((10,0)--(13,0)--(13,1)--(10,1)--cycle, gray);
draw((0,1)--(0,0)--(13,0));
draw((13,0)--(13,1), linewidth(2)+red);
draw((13,1)--(13,2)--(12,2), b);
draw((12,2)--(12,3)--(11,3), lb);
draw((11,3)--(11,4)--(10,4), b);
draw((10,4)--(8, 4), lb);
draw((8,4)--(8, 3)--(7,3), b);
draw((7,3)--(5,3), lb);
draw((5,3)--(5,2)--(4, 2), b);
draw((4,2)--(2,2), lb);
draw((2,2)--(2,1)--(1,1), b);
draw((1,1)--(-1,1), lb);
draw((2,1)--(13,1)); draw((5,2)--(12,2)); draw((8,3)--(11,3));
draw((1,1)--(1,0)); draw((2,1)--(2,0)); draw((3,2)--(3,0)); draw((4, 2)--(4, 0)); draw((5,2)--(5,0)); draw((6, 3)--(6,0)); draw((7,3)--(7,0)); draw((8,3)--(8, 0)); draw((9, 4)--(9, 0)); draw((10, 4)--(10,0)); draw((11,3)--(11,0)); draw((12,2)--(12,0));
[/asy][/asy]
Here, upward growth is now contained.
Same formatting as above; red is the first move, after that, we have alternating shades of blue.
This isn't the exact method I used in my solution because I didn't fill the remaining part out to be a rectangle in between sealing off sides, but this is a pretty good representation of a solution to this problem. The idea here is that the lower side is kept "at bay" with only one levee a turn while the remaining two/three sides are sealed off with the use of two additional levees per turn. And for the IMO TST versionIn actuality, you only need $1 + \varepsilon$ additonal levees per turn (i.e. what you get in the IMO problem) to eventually seal the rest of the sides off, because only one per turn is necessary to keep said side at base and you can eventually use the $\varepsilon$ levees to seal off the side after a considerable number of moves.
A lot of other kinds of solutions won't work because they try to keep two sides at bay or they try to seal off two sides at once, which won't work.
[asy][asy]
pen lb = linewidth(1.5)+rgb(0,130,255);
pen b = linewidth(1.5)+rgb(0,50,255);
fill((14,0)--(15,0)--(15,2)--(14,2)--cycle, gray);
draw((0,1)--(15,1));
draw((3, 2)--(16, 2));
draw((6,3)--(16,3));
draw((9, 4)--(16,4));
draw((12,5)--(15,5));
draw((1,0)--(1,2));
draw((2,0)--(2,2));
draw((3,0)--(3,2));
draw((4,0)--(4,3));
draw((5,0)--(5,3));
draw((6,0)--(6,3));
draw((7,0)--(7,4));
draw((8,0)--(8,4));
draw((9,0)--(9,4));
draw((10,0)--(10,5));
draw((11,0)--(11,5));
draw((12,0)--(12,5));
draw((13,0)--(13,6));
draw((14,0)--(14,6));
draw((15,1)--(15,4));
draw((14,0)--(15,0)--(15,1), linewidth(1.3)+red);
draw((15,1)--(16,1)--(16,2), b);
draw((16,2)--(16,4), lb);
draw((16,4)--(15,4)--(15,5), b);
draw((15,5)--(15,6)--(14,6), lb);
draw((14,6)--(12,6), b);
draw((12,6)--(12,5)--(11,5), lb);
draw((11,5)--(9,5), b);
draw((9, 5)--(9, 4)--(8,4), lb);
draw((8, 4)--(6, 4), b);
draw((6, 4)--(6, 3)--(5, 3), lb);
draw((5, 3)--(3, 3), b);
draw((3, 3)--(3, 2)--(2, 2), lb);
draw((2, 2)--(0, 2), b);
draw((0,2)--(0,0), lb);
draw((14,0)--(13,0)^^(12, 0)--(11, 0)^^(10, 0)--(9,0)^^(8, 0)--(7, 0)^^(6, 0)--(5, 0)^^(4,0)--(3,0)^^(2,0)--(1,0), b);
draw((13,0)--(12,0)^^(11,0)--(10, 0)^^(9,0)--(8,0)^^(7,0)--(6,0)^^(5,0)--(4,0)^^(3,0)--(2,0)^^(1,0)--(0,0), lb);
[/asy][/asy]
anser
17.12.2019 06:42
We can draw a square containing all initially flooded cells; let the side length be $s$. We will prove the problem when the all cells inside this square are initially flooded, since removing initially flooded cells does not harm Vulcan. In this four-step construction, Vulcan will build 3 new walls each turn.
The following diagrams include the square of side length $s$ outlined in green, the flooded cell boundary outlined in blue, the newly built walls in red, and the previously built walls in black.
Step 1[asy][asy]
pair A, B, C;
A = (-15, 0); B = (0, 0); C = (0, -15);
draw(A--B--C, red+linewidth(2));
pair X, Y;
X = (-10, 0); Y = (0, -10);
draw(A--X, blue);
draw((-10, 0)--(-10, -1)--(-9, -1)--(-9, -2)--(-8, -2)--(-8, -3), blue);
draw((0, -15)--(0, -10)--(-1, -10)--(-1, -9)--(-2, -9)--(-2, -8)--(-3, -8), blue);
draw((0, -15)--(-1, -15)--(-1, -16)--(-2, -16)--(-2, -17)--(-3, -17), blue);
draw((-15, 0)--(-15, -1)--(-16, -1)--(-16, -2)--(-17, -2)--(-17, -3), blue);
draw((-25, -10)--(-25, -15)--(-24, -15)--(-24, -16)--(-23, -16)--(-23, -17)--(-22, -17), blue);
draw((-25, -10)--(-24, -10)--(-24, -9)--(-23, -9)--(-23, -8)--(-22, -8), blue);
draw((-15, -25)--(-10, -25)--(-10, -24)--(-9, -24)--(-9, -23)--(-8, -23)--(-8, -22), blue);
draw((-15, -25)--(-15, -24)--(-16, -24)--(-16, -23)--(-17, -23)--(-17, -22), blue);
draw((-4.5, -6.5)--(-6.5, -4.5), dotted+blue+linewidth(2));
draw((-20.5, -6.5)--(-18.5, -4.5), dotted+blue+linewidth(2));
draw((-20.5, -18.5)--(-18.5, -20.5), dotted+blue+linewidth(2));
draw((-4.5, -18.5)--(-6.5, -20.5), dotted+blue+linewidth(2));
draw((-15, -15)--(-15, -10)--(-10, -10)--(-10, -15)--cycle, heavygreen);
label("$s$", (-12.5, 0), N); label("$2s$", (-5, 0), N);
[/asy][/asy]
In Vulcan's first $2s$ turns, he will build the top right corner of the levee such that the top and right walls are $2s$ away from the top and right sides of the square. This is possible because only immediately after $2s$ turns does the flood boundary reach the levee.
Step 2[asy][asy]
draw((-50, -15)--(-50, 0)--(-15, 0), red+linewidth(2));
draw((-15, 0)--(0, 0)--(0, -15), black+linewidth(2));
draw((0, -15)--(0, -40), red+linewidth(2));
draw((-15, -15)--(-15, -10)--(-10, -10)--(-10, -15)--cycle, heavygreen);
draw((-50, -15)--(-49, -15)--(-49, -16)--(-48, -16)--(-48, -17)--(-47, -17)--(-47, -18)--(-46, -18), blue);
draw((0, -40)--(-1, -40)--(-1, -41)--(-2, -41)--(-2, -42)--(-3, -42)--(-3, -43)--(-4, -43), blue);
draw((-15, -50)--(-10, -50), blue);
draw((-10, -50)--(-10, -49)--(-9, -49)--(-9, -48)--(-8, -48)--(-8, -47), blue);
draw((-15, -50)--(-15, -49)--(-16, -49)--(-16, -48)--(-17, -48)--(-17, -47)--(-18, -47)--(-18, -46), blue);
draw((-7, -46)--(-5, -44), blue+dotted);
draw((-19, -45)--(-45, -19), blue+dotted);
label("$3s$", (-7.5, 0), N); label("$7s$", (-65/2, 0), N); label("$3s$", (-50, -7.5), W); label("$5s$", (0, -55/2), E);
[/asy][/asy]
In each of the next $5s$ turns, Vulcan will build one wall downward on the right side of the levee and two walls to finish $7s$ of the top wall and continue downward on the left side. The left side of the flood boundary just reaches the left side of the levee after $7s$ turns in total.
Step 3[asy][asy]
draw((-50, -15)--(-50, 0)--(-15, 0), linewidth(2));
draw((-15, 0)--(0, 0)--(0, -15), linewidth(2));
draw((0, -15)--(0, -40), linewidth(2));
draw((-15, -15)--(-15, -10)--(-10, -10)--(-10, -15)--cycle, heavygreen);
draw((0, -40)--(0, -65), red+linewidth(2));
draw((-50, -15)--(-50, -65), red+linewidth(2));
draw((-50, -40)--(-49, -40)--(-49, -41)--(-48, -41)--(-48, -42)--(-47, -42)--(-47, -43)--(-46, -43), blue);
draw((0, -65)--(-1, -65)--(-1, -66)--(-2, -66)--(-2, -67)--(-3, -67)--(-3, -68)--(-4, -68), blue);
draw((-15, -75)--(-10, -75), blue);
draw((-10, -75)--(-10, -74)--(-9, -74)--(-9, -73)--(-8, -73)--(-8, -72), blue);
draw((-15, -75)--(-15, -74)--(-16, -74)--(-16, -73)--(-17, -73)--(-17, -72)--(-18, -72)--(-18, -71), blue);
draw((-7, -71)--(-5, -69), blue+dotted);
draw((-19, -70)--(-45, -44), blue+dotted);
label("$10s$", (-25, 0), N); label("$3s$", (-50, -7.5), W); label("$8s$", (0, -20), E); label("$10s$", (-50, -40), W); label("$5s$", (0, -105/2), E);
[/asy][/asy]
In each of the next $5s$ turns, Vulcan will build two walls on the left side of the levee and one wall on the right, so the left and right walls are equal in length.
Step 4[asy][asy]
draw((-50, -15)--(-50, 0)--(-15, 0), linewidth(2));
draw((-15, 0)--(0, 0)--(0, -15), linewidth(2));
draw((0, -15)--(0, -40), linewidth(2));
draw((-15, -15)--(-15, -10)--(-10, -10)--(-10, -15)--cycle, heavygreen);
draw((0, -40)--(0, -65), linewidth(2));
draw((-50, -15)--(-50, -65), linewidth(2));
draw((-50, -65)--(-50, -145)--(0, -145)--(0, -65), linewidth(2)+red);
draw((-50, -110)--(-49, -110)--(-49, -111)--(-48, -111)--(-48, -112)--(-47, -112)--(-47, -113)--(-46, -113), blue);
draw((0, -135)--(-1, -135)--(-1, -136)--(-2, -136)--(-2, -137)--(-3, -137)--(-3, -138), blue);
draw((-15, -145)--(-10, -145), blue);
draw((-10, -145)--(-10, -144)--(-9, -144)--(-9, -143)--(-8, -143), blue);
draw((-15, -145)--(-15, -144)--(-16, -144)--(-16, -143)--(-17, -143)--(-17, -142)--(-18, -142)--(-18, -141), blue);
draw((-7, -141)--(-5, -139), blue+dotted);
draw((-19, -140)--(-45, -114), blue+dotted);
label("$10s$", (-25, 0), N);
label("$13s$", (-50, -65/2), W); label("$16s$", (-50, -105), W);
[/asy][/asy]
In the final $14s$ moves, we increase the length downward of one of the left or right walls by 1 and the other by 2. Once the total length of the left or right wall reaches length $29s$, we begin constructing the bottom wall of the levee. Note that after these $14s$ moves (and $26s$ moves in total), the bottom edge of the flood boundary just hits the bottom of levee ($26s$ below the bottom edge of the green square).
somewhere123
09.06.2021 06:45
为什么我无法下载这个文档?
wamofan
09.06.2021 06:51
somewhere123 wrote: 为什么我无法下载这个文档? Translated from Google Translate: somewhere 123 (in english) wrote: Why can't I download the document?
Apple321
09.06.2021 17:43
wamofan wrote: somewhere123 wrote: 为什么我无法下载这个文档? Translated from Google Translate: somewhere 123 (in english) wrote: Why can't I download the document? what document-