Jumping frog problem

Question

Consider $n \ (>1)$ lotus leaves placed around a circle. A frog jumps from one leaf to another in the following manner. It starts from some selected leaf. From there, it skips one leaf in clockwise direction and jumps to the next one. Then it skips exactly $2$ leaves in clockwise direction and jumps to the next one. Then the frog skips $3$ in clockwise direction and so on. Suppose it turns out that if frog continues this way all leaves are visited by the frog. Show that $n$ cannot be odd.

My attempt,

Let frog be initially placed at leaf named $0$, and name the remaining leaves $1$, $2$ , $3$... $n - 1$ in clockwise direction. After $k$ moves the frog will be on label number $0+(1+1)+(2+1)+\ ...\ + (k+1) = k (k+3)/2$.

Thus the question reduces to proving that there does not exist any $i$ such that $n = 2i+1$ and the congruence stated below is satisfied for all $t$ for some value of $k$:

$k(k+3)/2 \equiv t \,\pmod n, \;\; 0\leq t \lt n$

Answer 1

Label the $n$ leaves as$\;0,...,n-1,\;$ordered counterclockwise from the starting leaf.

Let $f(k)$ be the position of the frog after $k$ steps.

\begin{align*} \text{Then}\;\;f(k) &= 2 + 3 + \cdots + (k+1) \;\;\text{mod}\;n\\[4pt] &= {\small{\frac{k(k+3)}{2}}} \;\;\text{mod}\;n\\[4pt] \end{align*}

Since jump number $(n-1)$ skips $(n-1)$ leaves and lands on the next, it follows that for all $n$,

$$f(n-1) = f(n-2)$$

Next, suppose $n$ is odd.

Suppose $a,b$ are nonnegative integers such that $a \equiv b \pmod n$.

\begin{align*} \text{Then}\;\;2(f(a) - f(b))&= 2\left({\small{\frac{a(a+3)}{2}}} - {\small{\frac{b(b+3)}{2}}}\right) \;\;\text{mod}\;n\\[4pt] &=\bigl(a(a+3)\bigr) - \bigl(b(b+3)\bigr) \;\;\text{mod}\;n\\[4pt] &=(a^2 + 3a) - (b^2 + 3b) \;\;\text{mod}\;n\\[4pt] &=(a^2 - b^2) + (3a-3b) \;\;\text{mod}\;n\\[4pt] &=(a-b)(a+b+3) \;\;\text{mod}\;n\\[4pt] &=0\qquad\text{[since $a \equiv b \pmod n$]}\\[12pt] \implies\;2(f(a) - f(b)) &\equiv 0 \pmod n\\[4pt] \implies\;f(a) - f(b) &\equiv 0 \pmod n\qquad\text{[since n is odd]}\\[4pt] \implies\;f(a) &= f(b)\\[4pt] \end{align*}

If follows that for odd $n$, the frog lands only on positions in the $n$-term sequence

$$f(0), f(1), f(2),...,f(n-1)$$

but then, since $f(n-1) = f(n-2)$, it follows that the frog lands only on positions in the $(n-1)$-term sequence

$$f(0), f(1), f(2),...,f(n-2)$$

hence the frog does not land on every leaf.

Thus, if the frog does land on every leaf, $n$ must be even.

Answer 2

Hint: After $n$ turns the frog is back where it started, by your formula. (If $n$ is odd then $n\mid n(n+3)/2$.) It is also about to make a jump of length $2$ (mod $n$). So in the next set of $n$ jumps it will visit the same locations as the first $n$, in the same order, and this pattern will repeat. So it suffices to show that the frog doesn't visit all the locations in the first $n$ jumps.

Answer 3

Since $n$ is odd $2$ is a unit in the ring $\mathbb{Z}/n\mathbb{Z}$. Thus you can simplify your equation to:

$k(k+3)\equiv 2t \text{ mod }n$

As mentioned before $2$ is a unit thus for any $s\in\mathbb{Z}/n\mathbb{Z}$ there is a $t\in\mathbb{Z}/n\mathbb{Z}$ such that $2t\equiv s \text{ mod }n$. Therefore it suffices to show that there is a $s\in\mathbb{Z}/n\mathbb{Z}$ such that for all $k\in\mathbb{Z}/n\mathbb{Z}$:

$k(k+3)\not\equiv s \text{ mod }n $

There are $n$ choices for $s$ and $k$ (namely $0,1,\dots,n-2,n-1$). If there are $k,k'\in\mathbb{Z}/n\mathbb{Z}$ ($k\not\equiv k'$) such that $k(k+3)\equiv k'(k'+3)$ then there are at most $n-1$ different $s\in\mathbb{Z}/n\mathbb{Z}$ such that:

$k(k+3)\equiv s \text{ mod }n $

If we choose $k=0$ and $k'=n-3$ we get $k(k+3)\equiv k'(k'+3)\equiv 0$. Therefore there has to be a choice for $s$ for which the equation above does not hold for any $k\in\mathbb{Z}/n\mathbb{Z}$.