A 'jumping' sequence is well defined?

Question

Imagine standing on the first square of an infinite sidewalk labelled $1,1,2,2,3,3,\dots$
Whenever you are on a square labelled $k$, you may jump $k$ squares in either direction to another square.

What is the minimal number of jumps required to reach the $n^{th}$ square ?

The sequence begins $0,1,2,5,3,6,9,4, \dots$ For example, the fourth term is $5$, because to get to the fourth square (labelled '$2$'), the quickest way is to jump: forward, forward, forward, forward, and backward.

One might need to draw the possible paths to get familiar with the sequence.

One can prove that it’s possible to reach any square, so this sequence is well defined. The question is how to prove this.

$\textbf{Prove that all squares can be reached by such jumps }$

Answer 1

TLDR

Yes, the sequence is well defined. For any target square $m>0$ we can show it's possible to reach $m$ from a strictly smaller square.

• If $m$ is 1 or 2 mod 3, we can find a smaller square $r$ and then take a single "right" step to get from $r$ to $m$.
• If $m$ is 0 mod 3, we can find a smaller square $r$ and then step "right, right, left" to get from $r$ to $m$. (Exception: this only works if $m>3$. To handle $m=3$ we just check that single case by hand.)

All the details are explained below. I'm just adding this section at the top so you don't lose sight of the overall idea among all the fiddling with modular arithmetic.

Full proof

I'll index the squares as $0, 1, 2, \cdots$, so square $k$ has the label $s(k) = \lfloor \frac k 2 \rfloor + 1$. Fix a target square $N > 0$; I'll prove that it's possible to travel from square $0$ to square $N$.

Let $S = \{k \in \mathbb{Z}_{\ge 0} : \text{it's possible to travel from $k$ to $N$}\}$ and let $m$ be the smallest integer in $S$. Our goal is to show $m=0$. To do that, we'll rule out all other options using several subcases.

1. As noted in the question statement, it's easy to find paths from square $0$ to squares $1, 2, 3$, so we must have $m > 3$. (Otherwise we could just travel from 0 to $m$ and then from $m$ to $N$, which would contradict the choice of $m$.)
2. If $m$ is 1 mod 3, we can write $m = 3a+1$ and define $r = 2a$. Then $r + s(r) = 2a + (a+1) = m$, so we can step forward from $r$ to $m$, which means we can travel from $r$ to $N$. But $r < m$, contradicting minimality of $m$.
3. If $m$ is 2 mod 3, we can write $m = 3a+2$ and let $r = 2a+1$. Then again we can check $r + s(r) = m$ but $r < m$, a contradiction.
4. If $m$ is 0 mod 9 and $m > 0$, let $m = 9b$ and $r = 8b$. Now $r + s(r) = 12b+1$; from there we can step forward again to $18b + 2$; and from there we can step backward to $9b = m$. But $r < m$ (since $m>0 \implies b>0$).
5. If $m$ is 3 mod 9 and $m > 0$, let $m = 9b+3$ and $r = 8b+3$; note $r < m$. Now from $r$ we can step forward to $12b+5$; then forward to $18b+8$; then backward to $9b+3 = m$.
6. If $m$ is 6 mod 9, let $m = 9b+6$ and $r = 8b+5$; note $r < m$. Then from $r$ we can step forward to $12b+8$; then forward to $18b + 13$; then backward to $9b+6 = m$.

Putting all of those cases together, we conclude $m$ can't be any positive integer, so we must have $m = 0$ and thus square $N$ is reachable from square $0$ after all.