Frog Jump Problem

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.

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?