Ytukyg

The frog game on a Tree:

• Default start of the game is placing one frog on each node (vertex).


• The goal is to move all the frogs to one single node.


• A single move consists of moving all $n$ frogs from node $A$ to nonempty node $B$, which is allowed only if there exists a path from $A$ to $B$ containing exactly $n$ unique edges. Node $B$ is called nonempty if there is at least one frog on it.


• If it is possible for all frogs to end up on some node $N$ (the game is solvable at N), then that implies that the frog on node $N$ never moves during the game, hence that node will be called a lazy toad.

Question: How can one characterize lazy and non-lazy toad nodes within trees?

Spliting trees into sets and characterizing lazy toads within those sets

I was initially observing tree sets based on leafs, but Bob Krueger suggested in the comments that it's better to look at branching nodes instead. Indeed, this is a better way to look at the trees.

A branching node is a node of degree at least $3$.

I decided to observe $b$ branching node tree cases - sets of trees with $b$ branching nodes.

They are further split into sets $[m_1,m_2,dots,m_b]=$ a set of all trees whose branching nodes $b_1,b_2,dots,b_b$ have degrees $m_1,m_2,dots,m_b$.

$0$ Branching nodes case

This case is basically the Frog Jumping game showed on Numberphile.

Tree with $n$ nodes that is categorized under this case always looks like a simple chain:

1-2-3-...-(n-2)-(n-1)-n

This case was already fully solved at the linked video. I will formalize the proof below:

Theorem. All trees that have no branching nodes are always fully lazy (All
nodes are lazy toads).

Proof.

$(1)$ Given tree with $n$ nodes labeled as "$1-2-3-...-n$", it is always solvable at nodes $1$ and $n$ :

• If $n$ is odd, start at middle node $frac{n+1}{2}$. Then by repeated jumping "left-right" we end up with all frogs at node $n$. Symmetrically, repeated "right-left" jumps will solve the game at node $1$.




• If $n$ is even, we can start at $frac{n}{2}$ and by repeating "right-left" solve the game at $n$. Again, symmetrically, starting at $frac{n}{2}+1$ and repeating "left-right", solve the game at $1$.

If we can always solve the tree at leaf nodes ($1$ and $n$), then we can solve it at any node:

• Simply split the tree into two parts: "$1-2-dots-k$" and "$k-(k+1)-dots-n$". Now solve both parts at $k$ as explained in $(1).implies$ tree is solvable at node $k$, where $k$ is any node.

$$tag*{$blacksquare$}$$

$1$ Branching nodes cases

This case can be split into sub-cases $[m]$, where $[m]$ stands for the set of all trees with one branching node of degree $mge3$. Those trees will have at least $n=m+1$ nodes.

The $[n-1]$ tree set

If $m$ is not constant but set to $m=n-1$, where $n$ is the number of the nodes of the tree, then this set of trees is trivial. All of them look like a "sun" or "flower head"; Label nodes from $0$ to $n+1=m$, and let node $0$ be the node of degree $m$.

   3  2  1

     | /

  4 - 0 - m

    / | 

  5  ... m-1

Theorem. All trees in this set have exactly one lazy toad node, node $0$.

Proof.

To show that $0$ is lazy is trivial: For every other node, move its frogs to node $0$.

To show that the leafs are not lazy toad nodes (nodes $1dots m$):

The longest path in these trees is always $2$, which means you can't have more than $2$ frogs on any node other than the leaf node you are trying to solve the game at. This implies all other leafs must reach target leaf $k_0$ with at most $2$ frogs (since that's already their distance to it as well, it must be exactly $2$ frogs).

The only node that can supplement leaf nodes with frogs up to $2$ frogs is node $0$. After using node $0$ to bring leaf $k_1$ frogs to target leaf $k_0$, all other leafs will have no moves to bring their frogs to $k_0.implies$ game is not solvable at leaf $k_0$, regardless of leaf choices for $k_0,k_1$ as everything is symmetric.

$$tag*{$blacksquare$}$$

$1$ Branching nodes cases without [n-1] trees = The $[m]_0$ tree sets

Lets exclude examples from $[n-1]$ set, from sets $[m]$; Let $[m]_0$ be a set of all trees with one branching node of degree $mge3$, that have at least $m+2$ nodes.

For $m=3$:

Theorem. Trees in $[3]_0$ are all fully lazy for $nge9$. They are also fully lazy for $nlt9$ except for these $4$ examples with exactly one non-lazy toad node (colored in red) shown here:

For $m=4$:

Theorem. Trees in $[4]_0$ are all fully lazy for $nge15$. They are also fully lazy for $nlt15$ except for a finite set of examples which are sorted below:

• 
  $1$ non-lazy toad examples, $2$ non-lazy toads examples, $3$ non-lazy toads examples, $5$ non-lazy toads example, $6$ non-lazy toads examples.

For $mge5$:

Conjecture. Trees in $[m]_0$ are all fully lazy for $nge n_m$. They are also fully lazy for $nlt n_m$ except for a finite set of
examples with varying number of non-lazy toad nodes.

I believe one can compute solutions for enough examples to guess $n_m$ for some $[m]_0$ set and then prove it with help of an algorithm by reconstructing the solvability of nodes. The examples for $nlt n_m$ can be computed as there should be finitely many of them.

But solving each $m$ individually with mainly relying on a computation, won't solve this problem for all $[m]_0$ sets. A characterizations of these trees is needed that will help mathematically prove the laziness of nodes of these trees.

Question: Any ideas how to reach such characterization(s)?

$bge2$ Branching nodes cases

Each of these cases can be further split into sets $[m_1,m_2,dots,m_b]=$ set of all trees with $b$ branching nodes that have degrees $m_1,m_2,dots,m_b$.

Each of those sets should have their $n_{(m_1,m_2,dots,m_b)}$ such that all trees with $nge n_{(m_1,m_2,dots,m_b)}$ nodes are fully lazy, where set of trees with $nlt n_{(m_1,m_2,dots,m_b)}$ nodes will have a finite number of examples with varying number of non-lazy toad nodes.

Question: Any ideas how to effectively find $n_{(m_1,m_2,dots,m_b)}$?

For example, for $b=1$, I conjecture that it is enough to observe this type of trees:

   3  2  1

     | /

  4 - 0 - m - m+1 - m+2 - m+3 - ... - m+k-1 - m+k

    / | 

  5  ... m-1

And by finding $k_0$ such that all those trees are fully lazy for all $kge k_0$, we get $n_m$.