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 $m\ge3$. 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 $1\dots 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 $m\ge3$, that have at least $m+2$ nodes.
For $m=3$:
Theorem. Trees in $[3]_0$ are all fully lazy for $n\ge9$. They are also fully lazy for $n\lt9$ 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 $n\ge15$. They are also fully lazy for $n\lt15$ except for a finite set of examples which are sorted below:
For $m\ge5$:
Conjecture. Trees in $[m]_0$ are all fully lazy for $n\ge n_m$. They are also fully lazy for $n\lt 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 $n\lt 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)?
$b\ge2$ 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 $n\ge n_{(m_1,m_2,\dots,m_b)}$ nodes are fully lazy, where set of trees with $n\lt 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 $k\ge k_0$, we get $n_m$.