Baltic Way 2024 · Problem 6

Throughout the solution, we denote a corridor directly connecting caves $a$ and $b$ by $a b$. First we show that Erik can reverse his moves. Indeed, consider three caves $a, b, c$ such that $a b$ and $b c$ are corridors, and assume that Erik stands in the corridor $a b$. He can then perform the moves $a b \rightarrow b c \rightarrow c a \rightarrow a b$ in succession (Fig. 1} note that after each move, the edge he is about to walk to in the sequence has just appeared as a consequence of his last move). But this will take him back to where he started as well as make sure that the layout of the labyrinth has not changed. Hence after performing the first move, he can "undo" it by performing the remaining two moves in this sequence.

Figure 1

Figure 2

This means that it is enough to show that Erik can turn any layout into the star shape (i.e., a layout with one central cave that all the remaining caves are directly connected to), since if he can get from any layout to the star shape he can also get from the star shape to any layout. Let us prove this by induction on the number $n$ of caves.

For $n=3$, any allowed layout has the star shape, so let us assume $n \geq 4$. It is easy to see that there has to exist at least two caves, each of which being connected to only one other cave. These caves cannot be directly connected to each other (otherwise they could not be connected to other caves). Hence one of these two caves, say $v$, is such that Erik is not initially standing in the only corridor adjacent to it. By the induction hypothesis, Erik can then perform some sequence of moves that will transform the labyrinth excluding $v$ into the star shape with $n-1$ caves. Let the central cave of the star be $c$ and assume that Erik is standing in the corridor $c w$. We have to consider three cases for how $v$ is connected to other caves:

• The cave $v$ is directly connected to $c$. In this case we already have the star shape with $n$ caves, and so we are done.
• The cave $v$ is directly connected to $w$. In this case Erik can make the moves $c w \rightarrow w v \rightarrow v c$ (Fig. 2). Then the resulting layout has the star shape.
• The cave $v$ is directly connected to some other non-central cave $u$. In this case Erik can make the moves

$$w c \rightarrow c u \rightarrow u w \rightarrow u v \rightarrow v w \rightarrow w c \rightarrow w u \rightarrow u c$$

(Fig. 3). Then the resulting layout has the star shape. In all cases, we have shown that we can turn the labyrinth into the star shape. So we are done by induction.

Figure 3

Clearly, any $n$ that works must be a divisor of the number $45^{2}-1=2024$ of unit squares. Furthermore, it must not be greater than 45 , or else we cannot fit any $1 \times n$ rectangles in the grid. This leaves the options $n=1, n=2, n=4, n=8, n=11, n=22, n=23$ and $n=44$. Note that any divisor $d$ of a length $n$ that works also works, since we can just divide each of the $1 \times n$ and $n \times 1$ pieces into $1 \times d$ and $d \times 1$ pieces.

For $n=22$, we can cover the grid as in Fig. 4. By the above, this shows that $n=1, n=2$ and $n=11$ all work.

For $n=23$, we can cover the grid as in Fig. 5 .

Figure 4

Figure 5

The remaining possibilities are $n=4, n=8$ and $n=44$. All of these are divisible by 4 , and hence if any of them work $n=4$ would also have to work. However, $n=4$ does not work. Indeed, color gray all rows with row numbers congruent to 1 or 2 modulo 4 (Fig. 6). Then any $1 \times 4$ or $4 \times 1$ piece will cover an even number of gray squares. But there is an odd number of gray squares in total, since the number of gray rows is odd, as well as the length of any row, and the center square is white as it is in row 23 . So it is impossible to cover all of them.

Consequently, $n=1,2,11,22,23$ are the only values that work.

Figure 6