A puzzle with some jumping frogs

Question

(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$".

Answer 1

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:

Every valid tree with more than one vertex admits a nontrivial automorphism.

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.

Answer 2

Not an answer, but there is an algebraic reformulation of the problem which is equivalent when $n$ is a prime.

First, we assume that at the end of the process all the frogs wish to end up on leaf $0$. For each $1 \le k \le n$, we define $a_k$ to be the number of frogs that eventually land on leaf $k$ (so the frogs on leaf $k$ all jump to leaf $k+a_k \pmod{n}$). Also, set $a_0 = n$.

Since every frog that reaches leaf $k$ comes from some leaf $j$ with $j + a_j \equiv k \pmod{n}$, we get

$a_k = 1 + \sum_{j \ne 0,\ j + a_j \equiv k \pmod{n}} a_j.$

Multiplying the $k$th equation above by $f(k)$ where $f : \mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}$ is any function, and summing over all possible $k$, we get

$\sum_{k = 0}^{n-1} f(k)a_k \equiv \sum_{k = 0}^{n-1} f(k) + \sum_{k = 0}^{n-1} a_kf(k+a_k) \pmod{n}.$

If $f(0) \equiv 0 \pmod{n}$, we can simplify slightly by replacing all the sums by sums from $1$ to $n-1$ (since $a_0 \equiv 0 \pmod{n}$). Now the idea is to use the fact that if $n = p$ is prime, then functions $f : \mathbb{F}_p \rightarrow \mathbb{F}_p$ satisfying $f(0) = 0$ are the same as polynomials having no constant coefficient.

Theorem: If $n = p$ is prime, then the frogs can all end up on the same leaf if and only if there are $a_1, ..., a_{p-1} \in \overline{\mathbb{F}}_p$ such that for each $1 \le d \le 2(p-1)$ we have

$\sum_{k=1}^{p-1} a_k((a_k+k)^d - k^d) = \begin{cases}0 & p-1 \nmid d\\ 1 & p-1 \mid d\end{cases}.$

Proof: Let $a_0 = 0$. For each $k \in \mathbb{F}_p$, let $f_k$ be a polynomial of degree at most $2p-2$ having roots at each element of $(\{0, 1, ..., p-1\} \cup \{a_1+1, ..., a_{p-1}+p-1\})\setminus\{k\}$, and such that $f_k(k) = 1$. Writing $f_k(x) = \sum_{d=0}^{2p-2} c_d x^d$ and summing the given equalities with weights $c_d$ for $d \ge 1$ (together with a trivial equality with weight $c_0$), we get

$\sum_{k = 0}^{p-1} f_k(k)a_k = \sum_{k = 0}^{p-1} f_k(k) + \sum_{k = 0}^{p-1} a_kf_k(k+a_k),$

and by the choice of $f_k$ this is equivalent to

$a_k = 1 + \sum_{j + a_j = k} a_j.$

Make a directed graph on $\{0, ..., p-1\}$ with $j\rightarrow k$ whenever $j+a_j = k$. Note that every vertex $k$ has outdegree $1$ if $a_k \in \mathbb{F}_p$ and $0$ otherwise, that a vertex $k$ has a self-loop if and only if $a_k = 0$, and that every vertex $k$ with indegree $0$ has $a_k = 1$. More generally, for every vertex $k$ which is not part of a cycle, $a_k$ is congruent modulo $p$ to the number of vertices $j$ such that there is a directed path starting at $j$ and ending at $k$ (including $k$).

Since vertex $0$ has $a_0 = 0$ and therefore has a self-loop, the collection of vertices $j$ such that there is a directed path from $j$ to $0$ forms a rooted tree, directed towards $0$, and the number of vertices in this tree is congruent to $0$ modulo $p$. Since there are only $p$ vertices total in the whole digraph, every vertex belongs to this tree.

Thus the whole digraph corresponds to a rooted tree with root $0$, and it describes a strategy for the frogs to all jump to $0$.

---

Given the above result, it seems tempting to try to use Gröbner basis methods to attack the problem for small primes $p$. For $p = 3$ and using $d = 1,2,3$ we have, after renaming $a = a_1, b = a_2$, the system of equations

$a^2 + b^2 = 0, a^3 + b^3 + 2a^2 + 4b^2 = 1, a^4 + b^4 = 0.$

The first and third of these imply that $a^4 = b^4 = a^2b^2 = 0,$ so after raising both sides of the second equation to the second power we get $0 = 1$, a contradiction.

For $p = 5$, computations with Macaulay 2 show that the equations corresponding to $d = 1, 2, ..., 5$ give a contradiction. For $p = 7,$ after several hours Macaulay 2 claims that the equations corresponding to $d = 1, 2, ..., 7$ give a contradiction.

Answer 3

I have verified the result by computer for $n\le 60$. I have included simplified, working C++11 code below; you may need to add a -std=c++11 flag to compile. (My actual code has been changing frequently as I attempt different optimizations.) Beware: as with all code, it may be incorrect.

The strategy is to find possible configurations in the backwards/"dual game" as discussed by Will Sawin, David Speyer, and Gerhard Paseman below another answer. The output prints the number of configurations found for each K. For a given $N$, the smaller entries will agree with David's calculations regarding "local conflicts", but the larger ones diverge for two reasons: (1) global conflicts modulo $N$, and (2) distinct trees with identical leaves (ie "multiplicity" as discussed in the comments below this answer). The set possible[K] contains all possible configurations that can be collapsed from K frogs back to a single, fixed leaf. The configurations are encoded and manipulated using bit operations.

One lesson learned from the output is that it is usually (but not always) possible for $n-1$ of the $n$ frogs to end up on one leaf.

#include <iostream>
#include <set>

const int N = 32;
static_assert( N <= 64, "The optimizations herein use 64-bit integers." );

std::set<uint64_t> possible[N+1];

int main( ) {
    std::cout << "N=" << N << std::endl;
    possible[1].insert( {1UL} );
    for( int K = 2; K <= N; K++ ) { 
        for( int I = 1; I < K; I++ ) {
            for( uint64_t p : possible[I] ) {
                uint64_t from = ((p & ((1UL << (N-I)) - 1UL)) << I) | (p >> (N-I));
                for( uint64_t to : possible[K-I] ) {
                    if( (to & from) == 0 )
                        possible[K].insert( to | from );
                }
            }
        }
        std::cout << K << "\t" << possible[K].size() << std::endl;
    }
    std::cout << (possible[N].size() > 0 ? "Success!" : "Failure.") << std::endl;
    return 0;
}

Answer 4

Edit: As pertains to UPDATE 2, the post below gives references to settle the case of $\ell = 1$.

---

This is a bit long for a comment, but I thought it worthwhile in case the following is non-obvious:

It is quite easy to prove that if $n$ is a power of $2$ then there is a sequence of jumps that leads [to] all the frogs on the same leaf.

(Maybe this really is "quite easy to prove," but I would not have known this to be the case at a glance without a familiarity with the references included below...)

If you begin with a frog and have it jump $1$ leaf, then have the newly formed duo jump $2$ leaves, then have the newly formed trio jump $3$ leaves, etc, then you move around the leaves by $+1, +2, +3, \ldots$ and, since you are jumping in a circle of $n$ leaves, the positions of frogs jumping together are at the triangular numbers modulo $n$.

And so the assertion elsewhere in this thread, which (in particular) covers the quotation-pull above, is that this will be sufficient to reach all the leaves if $n$ is a power of $2$. Equivalently, the set of the first $n$ triangular numbers modulo $n$ is $\{0, 1, \ldots, n-1\}$ if $n$ can be written as a power of $2$.

In fact, the last statement is true with if replaced by iff, and this was the subject of a very nice write-up in the New York Times' Numberplay column as Daniel Finkel’s Circle-Toss Game. There is another proof of this proposition by induction here, which includes a pointer to an earlier proof by D Knuth in:

The Art of Computer Programming, Volume 3, Chapter 6.4. Excercise 20 in the second edition.

Of course, with respect to the main question:

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$?

just the "if" is covered: the strategy above (as proved in the three different references given) shows how to get all the frogs to the same leaf for $n$ being a power of $2$. The "only if" part is what remains difficult, since the OP is proposed in greater generality than the circle-toss game: instead of the frogs needing to jump together in the triangular number pattern already described, one has access to lots of other patterns. I have no new suggestions for the "only if" component, although perhaps seeing the different proofs mentioned above (I especially enjoy the "multi-ball argument" in the first link) could serve as some sort of inspiration.