1

There are $n$ leaves placed in a circle. A monkey travels around it in a peculiar manner. On his $1^{st}$ jumps he skips one leaf and lands on the other. On the next jump he skips two. Then he skips three and so on. Prove that if he has to land in every leaf at least once, $n$ cannot be odd.

Ruddie
  • 436
  • If you number the leaves as $0$ to $n - 1$, then you can find the leaf he stepped on after $N$ jumps as $i = \frac{N(N+1)}{2} \mod n$. The problem then becomes to show that either $1$) for all values of $i$ (the $i^\text{th}$ leaf) there exists a value $N$ such that $i = \frac{N(N+1)}{2} \mod n$ or $2$) there exists a value of $i$ such that no value of $N$ satisfies $i = \frac{N(N+1)}{2} \mod n$ (mind that $i$ can only take on values from $0$ to $n - 1$). – Jared May 12 '14 at 06:04
  • Does "skip one and land on the other" to start on $0$ and land on $1$ or land on $2$? – Hagen von Eitzen May 12 '14 at 06:06
  • My formula is wrong...you add one each time you jump. I'm assuming if you number the leaves as $0$, $1$, $2$, $3$, $4$, etc. then at first you land on $1$ then you skip $2$ and land on $4$. This means you add the skipped number plus one each time. So the actual value should be $i = N - 1 + \frac{N(N+1)}{2}$. So now you get $N = 1 \rightarrow i = 1$, $N = 2 \rightarrow i = 1 + 3 = 4$, $N = 3 \rightarrow i = 2 + 6 = 8$, etc. (convince yourself that with $0$-indexing these numbers are correct). – Jared May 12 '14 at 06:10
  • There should be a nice inductive proof but I'm not seeing it at this moment--perhaps someone else can figure it out. It should be as "simple" as assume for $n$ you do not touch all of the leaves therefore for $n + 2$ you do not touch all of the leaves and likewise if you assume for $n$ you do touch all of the leaves then for $n + 2$ you also touch all of the leaves. Then you only need to prove that for $n = 2$ you do touch all of the leaves and for $n = 3$ you do not touch all of the leaves. – Jared May 12 '14 at 07:14
  • Another way to the inductive proof would be to assume for $n$ you do touch all of the leaves therefore for $n + 1$ you do not and assume for $n$ you do not touch all of the leaves therefore for $n + 1$ you do. – Jared May 12 '14 at 07:16

1 Answers1

2

If he starts at leave $0$, he is on leave $\frac{k(k+1)}2\mod n$ after $k$ jumps (or $\frac{k(k+3)}2$ with another definition of "skip"; but the result does not change). Let $p=2m+1$ be an odd prime divisor of $n$. Then $2^{-1}x(x+1)$ and just as well $x(x+1)$ must attain all values modulo $p$. But $x(x+1)\equiv x(x-2m)=(x-m)^2-m^2$ so that $(x-m)^2$ must attain all values modulo $p$. But $m$ of the remainders are non-squares.

We conclude that $n$ cannot have an odd prime divisor. Hence $n$ must be a power of two. It can be odd, though, namely if $n=1$.

Hagen von Eitzen
  • 374,180