(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$.
NOTE: I previously asked this question on MSE and I got non answers.
UPDATE 1: aorq checked that the answer is YES for all $n \leq 50$.
UPDATE 2: It might be worth trying to solve first this relaxed version of the problem:
To each solution of the puzzle associate a directed graph on the vertexes $0,1,\ldots,n-1$, where a directed edge $i \to j$ means a jump of all the frogs from leaft $i$ to leaf $j$. Say that the solution has $\ell$ leader frogs if its associated directed graph has exactly $\ell$ sources.
For which $\ell$ is it true that the $n$ frogs can finally be all on the same leaf using a series of jumps with $\ell$ leader frogs, if and only if $n$ is a power of $2$?
We know that $\ell = 1$ does the job, since with only one leader frog the problem is equivalent to "For which $n$ are the first $n$ triangular numbers distinct modulo $n$" and the answer is "only for $n$ a power of $2$".
Best Answer
Following David Speyer's improvement, given a rooted tree on $n$ vertices, we number each vertex $v$ with an integer $i_v$ mod $n$ so that the root is numbered $0$ and, if vertex $v_1$ is a child of vertex $v_2$ then $i_{v_1}$ is $i_{v_2}$ plus the number of descendants of $v_1$ (including $v_2$).
We say a rooted tree is valid if all the vertices $v$ have distinct numbers $i_v$. Each solution to the frog-jumping puzzle with $n$ lilies gives a valid rooted tree.
I've just noticed a simplification:
We can express the condition "if vertex $v_1$ is a child of vertex $v_2$ then $i_{v_1}$ is $i_{v_2}$ plus the number of descendants of $v_1$ (including $v_2$)." in a way that does not involve the root. Given two vertices of a tree, connected by an edge, each vertex of the tree is on one side of the edge or the other. The descendants on the child vertex are exactly on that side, so saying $i_{v_1}=i_{v_2}$ plus descendents of $v_1$ is equivalent to saying that $i_{v_1}$ is $i_{v_2}$ plus the number of the $v_1$ side, which is equivalent to saying that $i_{v_2}$ is $i_{v_1}$ plus the number on the $v_2$ side, as the numbers on both sides add up to $n$.
One consequence of this is that the validity of a rooted tree does not depend on the root.
Edit: A variant of this argument in different language was given by Gerhard Paseman in the comments. I didn't read it very carefully and didn't understand his language.
This also allows me to construct $2^{ {m \choose 2}}$ valid rooted trees on $2^m$ vertices, as David Speyer predicted.
The argument proceeds by induction. Given a valid rooted tree $T$ on $2^m$ vertices, fix a vertex $v \in T$ and consider $T \cup T$, with the two copies connected $v$ to $v$, with only the root in the first $T$ preserved. This numbering will have the property that for $w$ in one copy of $T$ and $w'$ its mirror image in the other copy of $T$, $i_{w}= i_{w'} + 2^m$ - using the local description we can see the difference $i_w-i_{w'}$ is independent of $w$, and by setting $w=v$ we see the difference is $2^m$. This immediately implies the $i_w$ are different modulo $2^{m+1}$ - to be equal mod $2^{m+1}$, $i_{w_1}$ and $i_{w_2}$ must first be equal mod $2^m$, which implies because $T$ is valid that $w_1$ and $w_2$ are either equal or mirror images, hence equal.
If there are $2^{{m\choose 2}}$ trees on $2^m$ vertices, and we have $2^m$ choices for which vertex to join them at, this gies a total of $2^{{m\choose 2}+m}= 2^{{m+1 \choose 2}}$ possibilities on $2^{m+1}$ vertices.
It is easy to see that we don't double count here. Any tree has at most one edge with an equal number of vertices on both sides, so every tree arises from this construction in at most one way.
I think it's reasonable to conjecture that these are the only solutions.
Here's an equivalent formulation of this conjecture:
Under this assumption, we can inductively prove that every valid tree has the stated form.
First, note that no valid tree has an automorphism with a fixed vertex. We could take that point to be the root, and then the function $i_v$ would be automorphism-invariant and hence would not be injective.
Second, recall that every automorphism of a tree fixes either a vertex or an edge.
Given a nontrivial automorphism that fixes an edge, its square fixes both vertices on that edge. So its square must be trivial, because the tree has no nontrivail automorphisms with fixed points. Hence it is an involution that exchanges the two sides of the edge.
It remains to check that each side of the edge is individually a valid tree with $n/2$ vertices. But this is easy - for an automorphisms $\sigma$, the function $i_{\sigma(v)}-i_v$ is constant, and equal to $n/2$ for both sides of the fixed edge, hence equal to $n/2$ everywhere. Since distinct vertices have distinct $i-v$ modulo $n$, it follows that distinct vertices have distinct $i_v$ modulo $n/2$ unless they are mirror images, sodistinct vertices on the same side have distinct $i_v$ mod $n/2$ and hence each side s a valid tree on $n/2$ vertices.
This shows it comes from one step of my construction, applied to a valid tree. By induction, it comes from an iteration of my construction, starting with the $1$-vertex tree.
One can use this idea, and the fact that the only automorphism-free trees on $\leq 8$ vertices are the one-vertex tree, $E_7$, and $E_8$, to find all valid trees on $\leq 8$ vertices without a brute force search.
However, I don't see any possible way to prove a valid tree has an automorphism.
My previous post:
Here is a reformulation of the problem that might be interesting:
We can view a solution to the puzzle as a binary tree. Start with $n$ leaves for each of the $n$ frogs, unordered. At each point in time, each node of the tree without a parent will represent a lily with frogs on it. Whenever the frogs from one lily jump unto another lily, add a new node that is a parent of both, with the first lily on the left and the second lily on the right. Finally we end up with a single node, the root.
We can reconstruct the position of each frog by working backwards, from the top of the tree to the bottom. Set the root node to have position $0$, and then set the right child of any node to have the same position as its parent and the left child to have the same position as its parent, minus the number of leaves among its descendants. If all the leaves have distinct positions mod $n$, it is a valid tree, otherwise, it isn't.
So a very rough heuristic, assuming that a random binary tree has a $n!/n^n$ probability of having all distinct positions among its leaves, suggest that the number of valid solutions (which is smaller than the $f(n)$ calculated by abc, because we consider solutions up to equivalence) should be $C_{n-1} n!/n^n \approx ( 4/e)^n$, which goes to $\infty$ with $n$, but is however not so big for $n \leq 14$ (at most $6$). So perhaps a little more numerical data would be helpful?
However this heuristic is probably quite bad. To me it seems like different leaves can have the same position mod $n$ for at least two separate reason - local reasons, which force two nodes to have the exact same position, and global reasons where they are distinct but equal mod $n$. Probably these should be treated differently.