A grasshopper can jump along a checkered strip for $8, 9$ or $10$ cells in any direction. A natural number $n$ is called jumpable if the grasshopper can start from some cell of a strip of length $n$ and visit every cell exactly once. Find at least one non-jumpable number $n > 50$. (Egor Bakaev)
Problem
Source: Tournament of Towns Spring 2017 Junior A-level
Tags: combinatorics, Russia
Cycle
30.05.2020 03:45
We claim that $62$ is non-jumpable. To show this, color the $8$ left-most cells of the strip black, the next $10$ cells red, the next $8$ black, and so on, until we have $62$ total cells as shown. There are $32$ black cells and $30$ red cells. Observe that if the grasshopper jumps from a black cell, it must arrive at a red cell. But there are more black cells than red cells, hence $62$ is non-jumpable.
alexiaslexia
08.03.2021 16:34
This might seem like an original idea, but its main idea is duplicated from the problem $\textit{exchanging coins crossing huge gaps}$ here. $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{This Solution doesn't need Sections. Also, black equals void.}$ We claim that $\boxed{n = 63}$ is non-jumpable. Divide a strip of length $63$ into seven consecutively placed strips of length $9$. Color the second, fourth and sixth black, and the rest white. However, mark the squares at the end of the white strips in red.
Say the red cells, in order from left to right, to be $r_1,r_2,\ldots,r_8$. Observe that any jump from a white cell (a red-marked cell is also considered a white-colored one, at that) will move the grasshopper towards a black cell, except the jump is done from $r_i$ to $r_{i+1}$, or from $r_{i+1}$ to $r_i$, with $0 \leq i \leq 7$. Let this configuration to be jumpable. Now for each jump originating from a white cell (there are at least $35$ of those, which happens iff the last cell of the path is white), at most seven of them are to white cells. This is because any jump from $r_i$ to $r_{i+1}$ (or vice versa) is only to be used at most once. However, this will imply the existence of $28$ jumps ending in black cells, a contradiction. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$
$\color{cyan} \rule{25cm}{2pt}$
$\color{green} \text{Sec 1.}$ Aside from experimenting directly with $8,9$ or $10$, I spent a lot of time to do trial-and-error with jumps of length $2,3$. However, even for the case $n = 6$, it's really not obvious on how to construct or to disprove the construction of a path: one might traverse through the strip on the path
\[ 1 \Rightarrow 3 \Rightarrow 6 \Rightarrow 4 \Rightarrow 2 \Rightarrow 5\]with no clear indicating pattern.
The trouble also lies when combining two sets of moves, i.e. $2,3$ with $3,4$. Who is to say that $2$ and $4$ will travel to cells of same parity to be useful? Dividing into groups which are spread out didn't seem to work here, and I appealed that the fact $50 \sim 8^2$ seemed to steer the direction of the Solution.
Moreover, I also think most numbers are $2,3,4$-jumpable, because of the simple reason that the numbers in the same vicinity are $\textbf{very reachable from each other in almost any circumstance}$; or algebraically stated,
\[ \dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4} \geq 1 \]While $8,9,10$ creates path with big gaps. The most trouble seemed to be commuting 3 or 4 steps: there isn't an easy way to leave a good path from $1$ to $5$ without impacting four other squares.
$\color{cyan} \rule{25cm}{2pt}$
$\color{green} \text{Sec 2.}$ So, this led me naturally to consider the jumps inversely: the leftmost square labeled $1$ are $\textit{friends}$ with the cells 9,10,11 as they are within 1 jump of each other, and $2$ with 10,11,12 --- and natural lines separating the eighteen squares $1,2,3,\ldots,18$ start to form.
Remembering an idea I thought long ago: what if the closer the squares are to the even $\textbf{blocks}$ (instead of even $\textbf{individual squares}$), the more $``\text{center}"$ they are, as in the Serbian problem? After all, every square in the edge of the strip must have their next stop to be the second leftmost block (exactly like the Construction's Motivation there).
And not too long after that, I conjured five blocks from thin air just like the Serbian problem, but I noticed that I had lots of extra lives and only a few white-white edges. So, extending $n = 45$ to $n = 63$, the answer and Solution is extracted.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]Final Comments: I think this Solution is structurally identical to the above (official) Solution: rephrased this way, there are six edges $r_i \Rightarrow r_{i+1}$:
\[ 1 \Leftrightarrow 9, 9 \Leftrightarrow 19, 19 \Leftrightarrow 27, 27 \Leftrightarrow 37, 37 \Leftrightarrow 45, 45 \Leftrightarrow 55 \]with $35$ white squares and $27$ black squares. This coloring can also be rephrased as above, with the red cells $9,27,45$ joining the black/void rally and deleting the existence of the edges $r_i \Rightarrow r_{i+1}$, except possibly $55 \Rightarrow 63$.