(The following puzzle is ispired by this nice video of Gordon Hamilton on Numberphile)

In a pond there are $n$ leaves placed in a circle, for convenience they are numbered clockwise by $0,1,\ldots,n-1$. At the beginning, on each leaf there is a frog, so there are $n$ frogs. At each turn, the frogs can jump accordingly to the following rule: "If on leaf $j$ there are $k \geq 1$ frogs and if on leaf $(j + k) \bmod n$ there is at least one frog, then all the $k$ frogs on leaf $j$ can jump on leaf $(j + k) \bmod n$".

Is it true that the $n$ frogs can finally be all on the same leaf if and only if $n$ is a power of $2$?

It is quite easy to prove that if $n$ is a power of $2$ then there is a sequence of jumps that leads all the frogs on the same leaf. On the other hand, I checked by a brute force algorithm that no such sequence exists if $n \leq 14$ is not a power of $2$.

  • $\begingroup$ Can frogs jump simultaneously? Ie. can frogs from leaf $a$ jump to leaf $b$ in the same moment, when frogs from $b$ jump to $c$? $\endgroup$ – Jaroslaw Matlak Mar 7 '17 at 9:16
  • $\begingroup$ @JaroslawMatlak No, they can't. $\endgroup$ – user126526 Mar 7 '17 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy