AoPS - Problem

Source: USA TST for EGMO 2019, Problem 1 (adapted from IMO TST Problem 3)

Tags: combinatorics

62861

10.12.2018 20:04

A $3 \times 3$ grid of unit cells is given. A snake of length $k$ is an animal which occupies an ordered $k$-tuple of cells in this grid, say $(s_1, \dots, s_k)$. These cells must be pairwise distinct, and $s_i$ and $s_{i+1}$ must share a side for $i = 1, \dots, k-1$. After being placed in a finite $n \times n$ grid, if the snake is currently occupying $(s_1, \dots, s_k)$ and $s$ is an unoccupied cell sharing a side with $s_1$, the snake can move to occupy $(s, s_1, \dots, s_{k-1})$ instead. The snake has turned around if it occupied $(s_1, s_2, \dots, s_k)$ at the beginning, but after a finite number of moves occupies $(s_k, s_{k-1}, \dots, s_1)$ instead. Find the largest integer $k$ such that one can place some snake of length $k$ in a $3 \times 3$ grid which can turn around.

sqrt-1likepi

11.12.2018 10:04

The answer is $k = 5$. Label the chessboard as follows: $$ABC$$$$DEF$$$$GHI$$Then a snake of length 5 placed on $(A, B, C, F, E)$ can turn around using the following sequence of moves (only the first cell of the snake is listed): $A \rightarrow D \rightarrow G \rightarrow H \rightarrow I \rightarrow F \rightarrow E \rightarrow D \rightarrow A \rightarrow B \rightarrow C \rightarrow F \rightarrow E$. We now consider a snake of length $k > 5$. Define a snake to be "stuck" if there are no empty cells adjacent to $s_1$. Clearly if a snake gets stuck, it can not turn around, so in what follows we assume that the snake does not get stuck. Checkerboard the grid so that the center cell $E$ is white. Note that any two adjacent cells of the snake are opposite colors. Therefore, a snake of length at least 6 covers at least 3 black and at least 3 white cells. Each time the snake moves, the cell previously covered by the snake's tail (its last cell) is now exposed. Note that this cell cannot be reentered by the head (first cell) of the snake on the same move, since the head must move into a previously empty cell. Also, each time the snake's head is on a white cell, it must move onto a black cell. However, since the snake occupies at least 3 black cells at any given time, there is at most one possible black cell for it to move onto (we assume that at least one black cell is open since otherwise the snake would be stuck). Now consider the sequence of black cells (in order) in the snake's position $k$-tuple followed by the empty black cell if there is one. Each time the snake moves, one of two things happen to this sequence: 1) If the snake's head was on a black cell, the sequence stays the same since each black cell in the snake simply shifts one position down, with the last cell in the sequence becoming empty if it wasn't already. 2) If the snake's head was on a white cell, the cell at the end of the sequence moves to the beginning. This is because the last cell in the sequence was previously empty, so as we observed earlier the snake's head must move onto it. The other black cells in the snake simply shift one position down, again with a new cell possibly becoming empty. Therefore, the order of black cells in the sequence simply cycles. However, the order of the non-empty cells must reverse for the snake to have turned around. This is impossible, so a snake of length greater than 5 cannot turn around.

postcards

13.08.2019 07:52

The answer is $k=5,$ and a possible construction is putting $s_1s_2s_3$ as a line through the center. Now I will show $k=6$ doesn't work (clearly this finishes). Color the grid like a checkerboard, with the corners/centers being blue and the ``edges'' being white. The snake always covers 3 of the 4 white squares, because adjacent squares are different colors. Label the white squares as $(0,1,2,3)$, where 0 indicates the white square in the initial position that is uncovered, 1 indicates the white square with smallest index $s_i$, and so on for 2 and 3. Note that after every two moves, the snake moves into exactly one square of each color. When it moves into the white square, it only has one option to move $s_1$ into, so the ordered quadruple must change to $(1,2,3,0)$. Similarly, this becomes $(2,3,0,1)$ then $(3,0,1,2)$ then back to $(0,1,2,3)$. Thus, it can never reach the desired $(0,3,2,1)$, so $k=6$ doesn't work, as desired.