# Frog Jump Problem

Lotus leaves are arranged around a circle.

A Frog starts jumping from one leaf in the manner described below. In the first jump it skips one leaf,next jump it skips two,three the next jump and so on.

If the frog can reach all the leaves, show that number of leaves cannot be odd.

This was an entrance examination question in India for Mathematics.

-
This was a good question!!It took me almost 40 minutes to solve it! :P –  Abir Mukherjee May 12 '14 at 4:23
@AbirMukherjee I was supposed to solve this in 5-10 minutes.Competition in india is like nowhere else. –  Bharath G Ron May 13 '14 at 12:58
Bro I gave the same ISI exam! I know how tough it was as I myself took appx 40 mins for this question!! :) –  Abir Mukherjee May 13 '14 at 16:34
@BharathGRon One gets 15 minutes per question. (8 questions $\to$ 120 mins.) –  Ruddie May 14 '14 at 5:57
@AbirMukherjee did yougive CMI it was hell?? –  Bharath G Ron May 16 '14 at 12:52

Suppose that there are $m$ leaves, where $m$ is odd. If $m=1$ the frog obviously does reach every leaf, so we assume $m>1$. (In any case presumably one leaf cannot be "arranged around a circle".) The total number of leaves jumped up to stage $n$ is $\frac{1}{2}n(n+1)$, and the leaf arrived at is the $k$th from the start, where $$\frac{1}{2}n(n+1)\equiv k\pmod m\ .$$ If $k$ is odd then this congruence is equivalent to $$4n(n+1)\equiv 8k\pmod m$$ and hence to $$(2n+1)^2\equiv 8k+1\pmod m\ .$$ Suppose that this has a solution for every $k$. Since $8$ and $m$ are coprime, the values $8k+1$ include all residues modulo $m$, so $$(2n+1)^2\equiv l\pmod m$$ has a solution for every $l$. That is, every $l$ is a square modulo $m$. But this is not true.

-
Actually, this shows that the number of leaves cannot have an odd prime divisor. So $m$ must really be a power of two (which also covers the exceptional case $m=1$ left out from th eproblem statement). –  Hagen von Eitzen May 13 '14 at 15:04
@HagenvonEitzen, and conversely, if $m$ is a power of $2$ then the frog does eventually reach all leaves. Sketch of proof: let $m=2^t$ and consider the numbers $0,1,1+2,\ldots,1+\cdots+n$, where $n=2^t-1$. These are all different modulo $2^t$, because if $0\le a<b<2^t$ and $\frac{1}{2}a(a+1)\equiv\frac{1}{2}b(b+1)$ then$$2^{t+1}\mid(b-a)(b+a+1)\ .$$But one of $b-a$ and $b+a+1$ is odd, so $2^{t+1}$ is a factor of the other, and it is easy to see that this is impossible. So the frog has $m$ different "destinations" out of $m$ possibilities. –  David May 14 '14 at 0:21
. . . and in fact this suggests an alternative solution to the original problem. If $m$ is odd then $1+\cdots+k$ is a multiple of $m$ both for $k=m$ and for $k=m-1$. So the first $m$ "destinations" are not all different, and at least one must have been missed. And after the $m$th jump the whole procedure repeats (modulo $m$), so the missed destinations are never picked up. –  David May 14 '14 at 0:34

Suppose that we have numbered the leaves as $a_1$ , $a_2$ , $\cdots$ clockwise. We call this our initial $n$-tuplet. Now we view the problem as follows. Each time the frog jumps from $a_i$ to $a_j$ we consider a swapping of $a_i$ and $a_j$. Now since by hypothesis the frog reaches all the leaves, in our construction of the problem this is equivalent to the statement that we reach our initial $n$-tuple after those operations in an even number of steps.

Now this is easy. For sometime let us forget the problem and consider the following problem-

For any collection of $n$ distinct objects starting from a particular permutation, one reaches that particular permutation after $k$ steps by swapping two consecutive neighbours. Prove that $k$ must be even.

One solution is to consider a bijection between the distinct objects and the $n$-tuple and the say that the numbers $a_i$ and $a_j$ are said to be out of order if $\max (a_i,a_j)$ is at the left of the smaller. In that case, they form an inversion. Now prove that the interchange of two neighbors changes the parity of the number of inversions.

Now consider the following generalization of the above problem.

For any collection of $n$ distinct objects starting from a particular permutation, one reaches that particular permutation after $k$ steps. Prove that $k$ must be even.

The hint for the above problem is to note that any such random permutation consists of an odd number of the above restricted permutations.

Have you noted that in course of proving the equivalence (actually the generalization of the second problem is much more general) you have proved a much general version of the your problem?

-