Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Terms of use
Privacy Policy

More Mathematics
CTK Exchange

Games to Relax
Guest book
Recommend this site

Sites for teachers
Sites for parents

Manifesto: what CTK is about Buying a book is a commitment to learning Things you can find on CTK Email to Cut The Knot Recommend this page

Toads And Frogs Puzzle

The Toads And Frogs Puzzle is also known under the names of Hares and Tortoise and Sheep and Goats. With no animals at hand, it can be played with two kinds of coins. The following names still reflect on the essence of the activity: Hop, Skip, Jump and Traffic Jam.

N frogs are placed on N successive positions on the left of a string of squares; M toads occupy M rightmost squares. On the whole, there are M + N + 1 squares, so that just one square remains unoccupied.

Frogs only move rightward; toads move leftward. Every move is either a Slide to the nearby square or a Jump over one position, which is allowed only if the latter is occupied by a fellow of a different kind. In any case, no two animals are allowed in the same square.

The goal is to move toads into M leftmost positions and the frogs into N rightmost positions.

The number of toads and frogs can change between 1 and 5. Originally, N = M = 3. These are shown just above the string of squares. To change the values, click on either a little off its center line.

<hr> <h3> This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet. </h3> <hr>

For every combination of N and M, the puzzle has two solutions: one can start either towards right or left. In both cases, the total number of moves is MN + M + N. There are MN Jumps and M + N Slides.

There is another interesting fact. For every sequence of moves, we can form a string of letters S and J. S denotes a Slide, while J stands for a Jump. Because of the symmetry, there is no wonder that, when M = N, the two strings corresponding to the two solutions are identical. What's interesting is that the same is true even when M differs from N. In addition, the string of moves is always palindromic.

We can also look at the movements of the hole - the empty square. This can move either 1 (r) or 2 (R) places right, or 1 (l) or 2 (L) places left. Unless M = N, the string thus obtained is no longer palindromic. They are palindromic whenever M = N. Strings corresponding to the two solutions are also different. However, they are not unrelated!

At every stage of solution, when it comes to selecting the next move, you may have to select either between two jumps, or two slides or a jump and a slide. One approach to solving the puzzle is to develop a certain strategy of behavior in each of the three cases.

Once you figured out how to solve the puzzle, you may want to try a two dimensional variant.

References

  1. W.W.Rouse Ball and H.S.M.Coxeter, Mathematical Recreations and Essays, Dover, 1987
  2. E.R.Berlekamp, J.H.Conway, R.K.Guy, Winning Ways for Your Mathematical Plays, v1, A K Peters, 2001.
  3. E.R.Berlekamp, J.H.Conway, R.K.Guy, Winning Ways for Your Mathematical Plays, v2, Academic Press, 1982.

On Internet

  1. Traffic Jam

Copyright © 1996-2008 Alexander Bogomolny



Search:
Keywords: