8
$\begingroup$

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.


given image of the graph



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:

$\endgroup$

2 Answers 2

6
$\begingroup$

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!!

$\endgroup$
1
  • $\begingroup$ Congrats! It is a successful party! $\endgroup$
    – Vepir
    Dec 1, 2020 at 2:32
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Almost there! But I think you have a mistake: 678→9 (from 6 to 9) is not possible because 678 are 3 frogs, but frog 9 is 4 edges away from frog 6. (The path is 6-0-7-8-9.) $\endgroup$
    – Vepir
    Nov 30, 2020 at 22:28
  • 1
    $\begingroup$ Yep, can't count :-( Will try to fix. $\endgroup$ Nov 30, 2020 at 22:54
  • 1
    $\begingroup$ Your second attempt has a new mistake: In step 2. you use up 13, but then you use it again in step 4. as 13→14. (Hint: rot13(Lbhe svefg nggrzcg jnf pybfre gb gur fbyhgvba, engure guna lbhe arj nggrzcg.)) $\endgroup$
    – Vepir
    Dec 1, 2020 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.