*This is a cross-post from [math.stackexchange.com](https://math.stackexchange.com/q/3800570/318073)$^{[1]}$, since the bounty there didn't lead to any new insights.*

----------

For reference,

> The **Frog game** is the generalization of the *Frog Jumping (see it on [Numberphile](https://www.youtube.com/watch?v=X3HDnrehyDM))* that can be played on any graph, but by convention, we restrict the game to tree graphs. The *Frog Jumping* is equivalent to the case on "paths (tree graphs with exactly 2 leaves)" of the **Frog game**, which was resolved in the linked video.

The mechanics of the Frog game are in short,

> Given a tree graph and one frog on each vertex, the goal of the game is for all frogs to host a party on a single vertex of the graph. All of the $f$ frogs on some vertex can "jump" to some other vertex if and only if both vertices have at least one frog on them and both vertices are exactly $f$ edges apart from each other.
>
> If a sequence of "jumps" exists such that all frogs end up on a single vertex, then the party is successfully hosted on that vertex and we call that vertex a "lazy toad" (or just "lazy") because the frog that started there never jumped during the game.

Trivially, if $|V|=n$ is the number of vertices of some graph $G=(V,E)$, then every game on $G$ must end in $n-1$ moves (or less if the party isn't hosted, e.g. if the sequence of jumps is suboptimal and we can no longer make moves or if none of the vertices are lazy).


----------


Here, I'm trying to resolve the Frog game on "full binary trees".

Let $T_h=(V,E)$ be a full binary tree of height $h$. Denote its layers with $0,1,2,\dots,h$ where the root $r\in V$ is on the layer $0$ ("bottom layer"), where layer $i=1,2,\dots,h$ contains vertices $v_{i,j}$ labeled with $j=1,2,\dots,2^i$.

 That is, we have $|V|=2^{h+1}-1$. Let $h\in \mathbb N$ because $h=0$ is a single vertex which is trivial.

> **Conjecture.** For all $h\ge 4$, every vertex of $T_h$ is a "lazy toad" (is "lazy").

I couldn't prove the above, and for simplicity, my question is just about the root vertex:

> Let $h\in\mathbb N, h\ne 2$. Can we prove that the root $r$ of every such $T_h$ is a "lazy toad" (is "lazy")?

However, if the approach that can solve the root can be generalized to all other vertices, that's a big bonus.

----------

**Solving the root**

**Reduction.** We say that $T_h$ can be reduced to $T_s,s\le h-2$, if there exists a sequence of moves that can bring all frogs from the top $s$ layers $h,h-1,\dots,h-s+1$ to the root vertex.

I've managed to reduce $T_h$'s for all $h\in(2,20)$ by hand pretty easily. At most, I needed to consider only $31$ vertices or less to find a pattern that allows a reduction of entire layers, which is very efficient if you consider that $T_{19}$ has over a million vertices. It looks like that maybe an inductive argument would be able to solve the problem, but I did not manage to find a sufficient set of move sequences.

I'll summarize some immediate results below.

> **Trivial reduction.** If $h=2^t+t-2,t\ge 2$ and $T_{t-1}$ is solvable in root, then $T_h$ can be reduced to $T_{h-t}$.

In the above reduction, we are simply (at the top layers) solving $T_{t-1}$ subtrees in root and then jumping from that root to the root of $T_h$.

> **Necessary minimal reduction condition.** Let $h\gt2,a\ge2$. If reduction from $T_h$ to $T_{h-a}$ is possible, then there exists $b\in[0,h-a+1]$ and a partition of the number $(2^a-1)2^b$ into the layers $H=\{h,h-1,h-2,\dots,h-a+1\}$ where $(h-l)\in H$ is used at most $(2^{a-l-1})2^b$ times.

In the above condition, we say that "a partition is solvable" if we can bring the corresponding amounts of frogs to the corresponding layers. I.e. the above condition simply says that we must be able to partition the total number of frogs from the top layers (that we are reducing) into the corresponding vertices from which they can jump to the root.

It remains to show (or find an explicit set of move sequences that will imply) that at least one partition from the above condition is solvable. Surprisingly, for all $h\in(2,20)$ that I've solved so far, the solution was always available in the smallest or one of the smallest partitions ($a\le 5,b\le 3$) of no more than $31$. The $h=20$ is the first case that requires considering more than $31$ vertices.

I still do not see how to construct explicit move sequences for larger $h$ without tackling each one individually. Alternatively, could there be a way to prove that the root is lazy, without finding explicit move sequences?