Frog game on a dandelion graph

Question

There is some noise in the local pond. A group of frogs wants to host a birthday party!

There is a total of 22 lily pads in the pond, each housing a single frog. They are labelled as numbers from 0 to 21. To make their lives easier, each frog built one bridge to each of her neighbors. The frog 0 is the most popular frog and has frogs from 1 to 7 as her neighbors, where as frogs from 8 to 21 only have the preceding frog as a neighbor.

The 9th frog wants to celebrate her birthday. Can you guide all other frogs to her lily pad?

You can instruct all n frogs on a non-empty lily pad A to jump to some other non-empty lily pad B if and only if there exists a path between A and B that consists of exactly n unique bridges.

This is illustrated in the image below.

---

In other words, the rules of the frog game are formally given as:

The frog game

• The game is played on a graph whose vertices represent "lily pads" (Water lilies).

• At the start of the game, place one frog on each lily pad.

• The goal of the game is to move all frogs to a single given lily pad.

• You can move exactly all n frogs contained on lily pad A to some other lily pad B if and only if both lily pads are not empty (contain at least one frog) and there exists a path from A to B consisting of exactly n unique edges.

Then, the puzzle in the image is formally given as:

The goal of the puzzle is to solve the frog game on the 9th vertex of the given graph (see the image above). The graph consists of a root vertex labelled as 0th vertex, to which we connect 6 leaf vertices labelled as {1, 2, 3, 4, 5, 6} and one path graph of 15 vertices whose vertices are labelled as {7, 8, 9, ..., 21}.

You might want to print out the graph and use tokens to represent frogs. If not, it should not be a problem to use a pen and a paper (which is how I solved it eventually).

---

P.S. To warm up, can you see that the frog game can be solved on any vertex of a path graph?

This is because:

Place a path graph P_n with n vertices on a number line. If you start in the center vertex and alternate left and right jumps (or vice versa, depending on the parity of n), you can see that a path is easily solvable in the leaf vertices (vertices of degree 1).

Now, to solve a path graph P_n in an arbitrary vertex v, simply split it into two path subgraphs that share the vertex v as a leaf (and do not share any other vertices), and solve each subgraph using the leaf vertex strategy.

---

This puzzle was inspired by my generalization of a Numberphile puzzle, from a line to graphs. The graph given in this puzzle is special because it is the smallest counter-example to one of my old conjectures about "dandelion graphs".

To create the image of the puzzle (of the given graph), I used csacademy's graph editor.

P.S. Mathpickle has more puzzles like this one! See:

• https://mathpickle.com/project/lazy-toad-puzzles-counting-symmetry/

• https://mathpickle.com/project/lazy-toads-on-a-star/

Answer 1

Unique solution?

Group A:

Move 5 frogs to 0 from petals 1 through 5.
Move 6 frogs from 0 to 12 = 7 frogs on 12.
Move 7 frogs from 12 to 19 = 8 frogs on 19.
Move 1 frog from 20 to 21 = 2 frogs on 21.
Move 2 frogs from 21 to 19 = 10 frogs on 19.
Move 10 frogs from 19 to 9 = 11 frogs on 9.

Group B:

Move 1 frog from 13 to 14 = 2 frogs on 14.
Move 1 frog from 15 to 16 = 2 frogs on 16.
Move 2 frogs from 16 to 14 = 4 frogs on 14.
Move 4 frogs from 14 to 10 = 5 frogs on 10.
Move 5 frogs from 10 to 6 = 6 frogs on 6.
Move 6 frogs from 6 to 11 = 7 frogs on 11.
Move 7 frogs from 11 to 18 = 8 frogs on 18.
Move 1 frog from 17 to 18 = 9 frogs on 18.
Move 9 frogs from 18 to 9 = 20 frogs on 9.

And finally:

Move 1 frog from 8 to 7 = 2 frogs on 7.
Move 2 frogs from 7 to 9 = PARTY ON 9!!

Answer 2

There may be other solutions, but:

Step 1:

Gather all of the petals onto 0, via 1→0, 2→0, 3→0, 4→0, 5→0, 6→0

Step 2:

Do the only thing you can with the 7 frogs on 0: jump them to 13; then jump the 8 frogs there to 21. You now have 9 frogs on 21: 0, 1, 2, 3, 4, 5, 6, 13, 21.

Step 3:

The only jump these 9 frogs can make directly is to 12, but there you'll be stuck. In fact, we want to get them directly to 9. Thus we need 3 more frogs! The best thing to do is to get them from the adjacent lily pads, 18, 19 and 20, via 19→20, (19)(20)→18, (18)(19)(20)→21. We now have 12 frogs on 21, and can jump them all to 9.

Step 4:

Theoretically we are done, since the OP shows how to get all of the frogs in a path to one of its endpoints, so we can 7-8 to 9 and 10-17 to 9, but to be explicit: 8→7, 78→9; and 13→14, (13)(14)→12, (12)(13)(14)→15, (12)(13)(14)(15)→11, (11)(12)(13)(14)(15)→16, (11)(12)(13)(14)(15)(16)→10, (10)(11)(12)(13)(14)(15)(16)→17, and (10)(11)(12)(13)(14)(15)(16)(17)→9.

Original Incorrect Answer - Oh boy, am I dumb.

Here is one solution, there may be others:

The first thing to notice is that you can only use 0 once, so you need to be careful to centralize a some of the petals (1-6) first, and then move them all off 0. But how many to centralize? The obvious first thing to attempt is all: move all the 1-6 petals to 0, then jump 7 frogs to 13. But this quickly peters out: you jump 8 frogs to 21, then 9 frogs to 12, and you're stuck.

But you don't have to take all of the petals at once, because you can jump some frogs to a petal, and then jump them back to the 9. So let's try taking all of the petals except one to the 0, giving the series: 1→0, 2→0, 3→0, 4→0, 5→0, 012345→12, 012345(12)→19. We need two extra frogs to get back to 19, which we can grab via 20→21 and (20)(21)→19, and the whole mess 012345(12)(19)(20)(21) gets back to 9.

Next steps:

At this point you have a mass of frogs on 9, and single frogs on 6, 7, 8, 10, 11, and 13-18. Let's clear out the petal side first. We need three frogs on 6 to jump back to 9, which we can get with 8→7, 78→6 and 678→9. Now 10 and 11 get to 9 with 10→11, (10)(11)→9. Finally we have six frogs in a row between 13 and 18 which can be massed at 15 by the given path graph result (explicitly: 14→13, (13)(14)→15, 17→16, (16)(17)→18, (16)(17)(18)→15), and then finally this mass jumps to 9, finishing the puzzle.