Is the Frog game solvable in the root of a full binary tree? https://ift.tt/2YFqPih

Frog game

The Frog game is the generalization of the Frog Jumping (see it on Numberphile) that can be played on any graph, but by convention, we restrict the game to Tree graphs (see wikipedia).

The game is simple to play, but it can be hard to determine if it is solvable in a given vertex.

In short, given a graph, the goal of the game is for all frogs to host a party on a single vertex of that graph. Initially, every vertex has one frog. All of the $f$ frogs on some vertex can "jump" to some other vertex if they both have at least one frog on them and if they 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" because the frog that started there never jumped.

Formal rules

Let $v,w,u\in V$ be vertices of a graph $G=(V,E)$ and $n=|V|$ the number of vertices.

Let $f_m:V\to\mathbb N$ count the number of frogs on a given vertex where $m$ is the current declared move. A game takes $(n-1)$ moves to solve (if possible) and is played as follows:

• We start the game on move zero $m=0$ where each vertex has one frog $f_0(v)=1,\forall v\in V$.

• If it is move $m\lt n-1$ and the following conditions are met:

  1. There exist two vertices $v,w\in V$ that have frogs on them $f_m(v)\ge 1$, $f_m(w)\ge 1$.
  2. There exists a path from $v$ to $w$ containing exactly $f_m(v)$ unique edges.

• Then, a legal move (or jump) can be made and is denoted as $(v\to w)$. If the move is made, then the following transitions occur:

  1. All frogs jump from $v$ to $w$, that is, $f_{m+1}(v)=0,f_{m+1}(w)=f_m(v)+f_m(w)$.

  2. The remaining frogs don't move, that is, $f_{m+1}(u)=f_{m}(u),\forall u\not\in\{v,w\}$.

  3. We declare the next move $m+1$. (The game ends if we can't move.)

• We say that the game is solvable in some vertex $w$ if there exists a sequence of legal moves such that we end up moving all frogs to the vertex $w$, which means $f_{n-1}(w)=n$. Consequently, if the game is solvable in $w$ then $f_{n-1}(v)=0,\forall v\ne w$. The solvable vertex $w$ is called a "lazy toad" because the frog on the vertex $w$ never jumped during the game.

For some examples, you can visit a post about this game on mathpickle. There is also an included link to a google drive where all trees with less than $15$ vertices have been computationally solved and categorized by the number of vertices then by the number of non-solvable vertices.

Remark. I've asked a general question about this game before Frogs jumping on trees, which asks if we can characterize solvable and non-solvable vertices of certain sets of graphs, but that appears to be a hard problem. Here, I've decided to restrict the problem to binary trees and only observe the root vertex.

---

Question

Let $T_h=(V,E)$ be a full binary tree of height $h$. This means that it has layers $0,1,2,\dots,h$ where the root $r\in V$ is on layer $0$. That is, we have $|V|=2^{h+1}-1$. Let $h\in \mathbb N$ because $h=0$ is a single vertex which is trivial.

I would conjecture that for all $h\ge 4$, every vertex of $T_h$ is a "lazy toad" (is solvable).

However, 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 solvable) ?

Notation

Let $v(i,j)\in V$ be the $j$th non-root vertex on the layer $i=1,2,\dots,h$ where $j=1,2,\dots,2^i$.

Lets declare a shorthand notation for moves:

• "$(v\to w)$ then $(w\to u)$" to be equivalent to "$((v\to w)\to u)$".

• "$(v\to w)$ and $(u\to w)$" to be equivalent to "$(v\to w \leftarrow u)$".

For clarity, let $f=f_m(v)$ in "$\left(v\xrightarrow{f} w\right)$" stand for the number of frogs being moved.

Alternative suggestions for notation are welcome.

---

Examples (Reducing $T_3,T_4,T_5$ to $T_1$)

The fact that we can reduce examples to smaller examples makes me think that maybe induction is possible. Notice that $T_1$ was solved in the original version of the game where all vertices are on a line and that $T_2$ is not solvable, so $T_3$ is the first "real" case.

$$(h=1)$$ The trivial case $T_1$ is trivially solvable in all vertices:

• [1.1] In $r$ using legal moves $v(1,1)\xrightarrow{1} r$ and $v(1,2)\xrightarrow{1} r$ in any order.
• [1.2] In $v(1,1)$ by using moves $\left(r\xrightarrow{1} v(1,2)\right)\xrightarrow{2} v(1,1)$.
• [1.3] In $v(1,2)$ by using moves $\left(r\xrightarrow{1} v(1,1)\right)\xrightarrow{2} v(1,2)$.

$$(h\ne 2)$$ The second case $T_2$ is not solvable in the root. This can be checked by listing all move sequences.

$$(h=3)$$ Lets break down the $T_3$ case. This case can be looked as a "base" trivial $T_1$ case that has two trivial $T_1$ cases "connected" to every leaf vertex. Let the vertices of those four "connected" trivial cases $T^{(1)}_1,T^{(2)}_1,T^{(3)}_1,T^{(4)}_1$ be indexed as: $v_1,v_2,v_3,v_4$ and let the vertices of the "base" trivial $T^{(0)}_1$ case be indexed as $v_0$.

That is, we can observe the $T_3$ as "composition" of $T_1$'s:

Now we can see that the solution in the root of $T_3$ follows from the solution of $T_1$. That is:

1. solve the "connected" $(T^{(i)}_1,i\in\{1,2,3,4\})$'s in a leaf vertex using [1.3]: $$\left(r_i\xrightarrow{1} v_i(1,1)\right)\xrightarrow{2} v_i(1,2),$$

2. then do the moves $v_i(1,2)\xrightarrow{3} r_0$ for $i\in\{1,2,3,4\}$ to transfer those frogs to root $r_0$,

3. then finally just solve the base $T^{(0)}_1$ with [1.1]: $v_0(1,1)\xrightarrow{1} r_0$ and $v_0(1,2)\xrightarrow{1} r_0$.

That is, the $T_3$ case is solved using the solutions of the trivial $T_1$ case.

In other words, if we know the solutions of $T_1$, we can reduce the $T_3$ to $T_1$ again.

$$(h=4)$$ Similarly as in the previous case, we can observe $T_4$ as "composition" of two connected $T_2$'s to each of the two leafs of one "base" $T_1$. That is, we "reduce" the $T_4$ to $T_1$ by "solving" the four $T_2$'s by moving all frogs from their vertices to the root of the "base".

We can "reduce" ("solve") $(T^{(i)}_2,i\in\{1,2,3,4\})$'s using following two move sequences:

1. $v_i(2,1)\xrightarrow{1} v_i(1,1)$ and $v_i(2,2)\xrightarrow{1} v_i(1,1)$, then $\left(v_i(1,1)\xrightarrow{3} v(2,4)\right)\xrightarrow{4} r_0$.

2. $r_i\xrightarrow{1} v_i(1,2)$ and $v_i(2,3)\xrightarrow{1} v_i(1,2)$, then $v_i(1,2)\xrightarrow{3} r_0$.

The vertices from the first (second) move sequence are colored blue (green) here in the $T_2^{(i)}$:

After the reduction, we are left with the "base" $T_1$ which is solved with [1.1] from the trivial case. In other words, we essentially moved all frogs from layers $2,3,4$ of $T_4$ to the root, leaving us only with layers $0,1$ which is equivalent to $T_1$.

$$(h=5)$$ Similarly to previous two cases, this $T_5$ case can be reduced to $T_1$ by solving four $T_3$'s. That is, we can reduce the layers $2,3,4,5$ by moving all their frogs to the base root. To do this, there are three separate move sequences highlighted in the following image (each puts $5$ frogs in a leaf vertex before moving the frogs to the base root):

1. $\left(\left(v_i(2,1)\xrightarrow{1} v(3,1)\right)\xrightarrow{2} v_i(1,1)\xleftarrow{1} r_i\right)$, then $\left(v_i(1,1)\xrightarrow{4}v_i(3,8)\right)\xrightarrow{5}r_0.$

2. $\left(v_i(3,3)\xrightarrow{1} v_i(2,2)\leftarrow{1} v_i(1,2)\right)$, then $\left(\left(v_i(2,2)\xrightarrow{3} v_i(1,2)\right)\xrightarrow{4}v_i(3,2)\right)\xrightarrow{5}r_0.$

3. $\left(v_i(3,5)\xrightarrow{1} v_i(2,3)\xleftarrow{1} v_i(3,6)\right)\xrightarrow{3} v_i(3,7)$, then $\left(v_i(2,4)\xrightarrow{1}v_i(3,7)\right)\xrightarrow{5}r_0.$

$$(h\ge 6)$$ These examples so far motivate the following question:

Is the reduction from $T_h$ to $T_1$ by solving four $T_{h-2}$'s always possible?

This could be one way to solve the problem. On the other hand, are there any other reductions?

---

Reduction pattern based on $T_6,T_7$

Since reductions from $T_h$ to $T_1$ over $T_{h-2}$'s seem to get more complex as $h$ grows, this begs the question if there are any other simpler reductions.

It is sometimes possible to reduce $T_h$ to $T_{h-2}$ over $T_1$'s. Take a look at the following examples.

Let $k=0,1,2,\dots,2^{h-2}-1$. If we look at the $T_6$, we can reduce its top two layers (reuducing it to $T_{4}$) using the following:

1. $v(6,4k+1)\xrightarrow{1} v(5,2k+1)$ and $v(6,4k+2)\xrightarrow{1} v(5,2k+1)$,

2. $\left(v(5,2k+2)\xrightarrow{1} v(6,4k+3)\right)\xrightarrow{2} v(6,4k+4)$,

3. $\left(v(5,2k+1)\xrightarrow{3} v(6,4k+4)\right)\xrightarrow{6} r$.

Similarly, we can reduce the $T_7$ to $T_5$ by using steps 1., 2. from above but modifying step 3. as (Note that you also modify the layers from $5$ to $6$ and $6$ to $7$ in all steps, of course.)

3. $\left(v(7,4k+4)\xrightarrow{3} v(6,2k+1)\right)\xrightarrow{6} r$.

We can ask if there are any other trees $T_h$ whose top two layers can be reduced.

Notice that we are collecting $T_1$'s in this reduction, that they contain $3$ vertices (frogs) each and that the total number of used $T_1$'s in our move sequence(s) must be a power of $2$ to completely reduce the top two layers, where we have $2$ possible layers $\{h,h-1\}$ to put the frogs on before jumping to root. Because of this, it is meaningful to try to extend this pattern to the full binary trees of the following kind:

If $h\in\{3\cdot2^t,3\cdot2^t+1\},t\in\mathbb N$, for which $t$'s is such $T_h$ reducible to $T_{h-2}$?

This now does smell like something that would be used in an inductive proof. But, even if this pattern holds for all $t$, it alone is not enough. The question is, can we find a sufficient set of reduction patterns?

Let $s\lt h$ and $h\gt 2$. Is it true that every $T_h$ can be reduced to some $T_s$ ?

---

Trivial reduction pattern

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}$.

This is trivially true because the distance of the root of "$T_{t-1}$ that spans the top $t$ layers" to the "(base) root $r=r_0$", is precisely equal to $2^t-1$, which is the total number of frogs in $T_{t-1}$.

For example, if $t=4$ we have $h=18$. Solving top $t=4$ layers as a $(T_{t-1}=T_{3})$'s in root, puts $15$ frogs on a vertices that are on layer $15$. These frogs can jump to the root of $T_h$ which leaves us with $T_{h-t}=T_{14}$.

Both this and the previous reduction pattern are exponential and are not enough to cover all values of $h$ in the inductive argument. That is, we need more statements like this to cover all values.

---

Other examples

I've managed to find reductions for $T_h$ for $h$ up to $20$ by hand to show they are all solvable in the root, but I still don't see how I could complete the inductive argument or solve this problem in some other way for all $h\ne 2$.

For example, I can reduce $T_8,T_9,T_{10},T_{11}$ to $T_5,T_5,T_6,T_7$ respectively.

Then, $T_{12},T_{13}$ belong to $t=2$ from the above reduction pattern for $h\in\{3\cdot2^t,3\cdot2^t+1\}$ and can be reduced to $T_{10},T_{11}$. It is not as easy as $t=1$, but the move sequences do exist.

After those, I can reduce $T_{14},T_{15},T_{16},T_{17}$ to $T_{11},T_{11},T_{12},T_{13}$.

Then, $T_{18}$ belongs to $t=4$ of the trivial reduction pattern which means it can be reduced to $T_{14}$.

For $T_{19}$ I found a reduction to $T_{14}$,... and so on.

Note that these reductions are not the only ways to solve a tree in the root.

---

Necessary reduction condition

Notice that to reduce $T_h$ to $T_{h-a}$ for some $a\ge 2$, we need to move all frogs from top $a$ layers to the root. The number of frogs we are moving to the root in such reduction is $(2^a-1)2^{h-a+1}$. That is, we are shaving off the $T_{a-1}$'s at the top layers. For such a reduction to be possible, there must exist a set of moves that transfers the frogs to the root $r$

$$M_r=\{v(i,j)\xrightarrow{f_{i,j}}r\},\text{ where } i\in\{h,h-1,\dots,h-a+1\}.$$

Assuming such moves exist at some point in the game, they are legal only if $f_{i,j}=i$ where $i$ is the layer on which the vertex $v(i,j)$ is on. On the other hand, the sum of $f_{i,j}$'s must be equal to the total number of frogs that we are reducing (moving to root). That is, for $M_r$ to be able to exist, we necessarily need to be able to partition the number of frogs we are moving onto the corresponding layers, and this is essentially what we state in the necessary condition.

We also care if our move sequences repeat or have patterns (for example, see the use of $k$ in the $T_6,T_7$ reduction pattern), because then instead of considering all frogs at once, we can consider only $(2^a-1)2^{b},b\in[0,h-a+1]$ frogs for some $b$, and repeat the same move pattern $(2^{h-a+1}/2^b)$ times.

Based on all of this, we can state the following necessary condition:

(Necessary condition for reduction). 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.

Of course, the converse does not hold because this is only a necessary (not a sufficient) condition.

For an example, if we want a $T_h$ to $T_{h-2}$ reduction then we need to partition $3\cdot 2^b$ into $\{h,h-1\}$. If we assume that the solution is "simple", i.e. that all frogs are either on layer $h$ or layer $h-1$ (but not mixed between both layers), we get the following pattern:

• $h$ must either be of form $3\cdot 2^t$ or $3\cdot 2^t+1$. This was essentially our assumption on $h$ when we talked about extending the $T_6,T_7$ pattern. But now we also need a sufficient condition. That is, if we want to prove this is possible for every $t$, then we need to for every $t$ find a sequence of corresponding legal moves or prove it exists.

Solvable partitions?

Surprisingly, the above condition is already very useful (efficient). I have that for all $h\in(2,20)$ I've solved so far, I needed to consider only $31$ or less vertices ($a\le 5,b\le 3$) to show that all vertices can be reduced to the root (that we can send all frogs to the root).

For example, the $T_{19}$ has over a million vertices! But, to solve it, one needs to consider just one $T_4$ (which has only $31$ vertices) at the top layers to find a solution! (Consider $a=5,b=0$ and the corresponding partition $31=15+16$ is solvable.) That is, the reduction pattern of that $T_4$ can simply be repeated on all adjacent $T_4$'s in the top five layers, which gives us a reduction to $T_{14}$ which we have already solved by reduction to $T_{11}$ then to $T_5$ then to $T_1$.

Essentially, we need to prove that at least one of the partitions given by the "(Necessary condition for reduction)" always allows the reduction to a smaller binary tree (that the converse holds for at least one partition). Then by induction, we have that they are all reducible to $T_1$.

I don't yet see how to construct move sequences for all cases of $h$. Alternatively, I do not know if we can maybe prove it without explicit construction of solutions?

from Hot Weekly Questions - Mathematics Stack Exchange
Vepir