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 Pn 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 Pn 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: