Estonian Math Competitions

(a) Note that all three squares in the leftmost and rightmost columns must be traversed consecutively because along with both corner squares of either of the columns one has to traverse the middle square of the same column and this cannot be done twice. In no other column can one traverse all three squares consecutively because such column would divide the grid into two parts between which one could not move without visiting a square twice. Note also that one cannot traverse three or more consecutive squares of the middle row consecutively because such trajectory would also divide the grid into two isolated parts (Figures 15 and 16). For similar reasons, when visiting two consecutive squares of the middle row consecutively, the previous and the next square should be taken from one and the same row (either top or bottom). Hence apart from the first and the last column, every legal trajectory divides the middle row into pairs of squares that are visited consecutively. Therefore the required enumeration is impossible for odd $n$. For even $n$, one can choose for every pair of squares in the middle row the row where the previous and the next square are located (either top or bottom); the number of such pairs of squares is $\frac{n-2}{2}$, whence there are $2^{\frac{n-2}{2}}$ possibilities to choose the direction of continuation for every such pair of squares. The whole trajectory is determined by these choices. For writing numbers in the case of a fixed trajectory, there are $6n$ possibilities (2 possibilities to choose the direction and $3n$ possibilities to choose the initial square). Consequently, there are $6n\cdot 2^{\frac{n-2}{2}}=3n\cdot 2^{\frac{n}{2}}$ possibilities of the required enumeration for even $n$.

(b) One cannot start from the middle square of the leftmost column since either of the corner squares would become a dead end. Hence suppose w.l.o.g. that one starts from the top left corner and visits $k$ squares in the top row (inclusive of the initial square), where $1\le k\le n$ (Fig. 17). Going directly to the bottom row would generally divide the grid into two isolated parts; also turning to the right along the middle row would make it impossible to visit squares in the left and afterwards reach the rightmost column. Hence one should turn to the left along the middle row. Similarly we find that the leftmost part of size $3\times k$ of the grid should be traversed along Z-shape (Fig. 18). After that, one should follow similar rules to traverse the remaining part of size $3\times (n-k)$. Repeating the argument, we can see that every legal trajectory divides the grid into Z-shapes and S-shapes, whereby Z-shapes are immediately followed by S-shapes and vice versa. In every column but the last one we can choose whether to start a new letter or make the current letter wider. In the first column, we also can choose which corner to start in. Hence there are $2^n$ possibilities altogether.

Fig. 15 Fig. 16 Fig. 17 Fig. 18