Competition problem — Combinatorics

Library / /27 of 37

Combinatorics Difficulty 8.2 Shortlist Find the answer

A *snake of length $k$ * is an animal which occupies an ordered $k$ -tuple $(s_1, \dots, s_k)$ of cells in a $n \times n$ grid of square unit cells. These cells must be pairwise distinct, and $s_i$ and $s_{i+1}$ must share a side for $i = 1, \dots, k-1$ . 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.

Determine whether there exists an integer $n > 1$ such that: one can place some snake of length $0.9n^2$ in an $n \times n$ grid which can turn around.

Nikolai Beluhov

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine whether there exists an integer $n > 1$ such that one can place a snake of length $0.9n^2$ in an $n \times n$ grid which can turn around, we proceed as follows:

We construct a snake in an $n \times n$ grid by dividing the grid into $m$ vertically stacked rectangular blocks of size $w \times h$ , where $w = mh + m - 1$ . We then create a snake that zigzags through these blocks. By carefully moving the snake through the grid, we can show that it is possible for the snake to turn around.

Specifically, we can place a snake of length at least $rn^2$ for any $0 < r < 1$ . By choosing a sufficiently large $m$ and $h$ , we can ensure that the length of the snake approaches $0.9n^2$ as closely as desired. The snake can be reversed by a series of moves that involve wrapping around the grid and forming reversed blocks (R-blocks) at the top of the grid.

Thus, there exists an integer $n > 1$ such that one can place a snake of length $0.9n^2$ in an $n \times n$ grid which can turn around.

The answer is: \boxed{\text{Yes}}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.