| The Frog Puzzle: A Solution | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| There are essentially two key steps in the overall puzzle. First, you have to master the sequence of moves that get the frogs interchanged. Second, you have to determine the number of moves needed for any number of frogs. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Sequence of Moves | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Below is a sequence of moves that
will get six frogs (three on each side) where they want to go.
If you have four frogs on either side the sequence of moves is very similar. The basic idea is to set up a situation where the yellow frogs, say, can provide a way of letting the red frogs jump over them in succession. There is one key idea here that has to be kept in mind. That is, that you never want to be in a position where two frogs of the same colour are next to each other. If you reach that state, then the whole jumping business comes to a halt. So think ahead to make sure that you don’t get two frogs of the same colour next to each other. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| The Number of Moves | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The 3-frogs-a-side problem is non-trivial.
When they do manage to get the frogs interchanged, it is well worth verbalizing
the pattern of moves. The challenge then is to predict the number
of moves that it takes to complete the problem with any number of frogs
on each side. To do this it may help to construct a table such as
the one below.
You might like to fill in the entries
for 6, 7 and 8 frogs-a-side or, at the very least, guess what these values
might be. It might help to look at it another way. How many
positions (rather than moves) are there during the jumping? If you look
at the sequence of moves we gave for three frogs a side above, this will
be 16. The initial position, before any frogs have moved, will be
counted as one of the positions. This leads to a more manageable
pattern. To help to see this, construct a table similar to the one
above. Here we add one to every entry in the second row of the table
above. Is the pattern clearer?
It certainly looks as if the number of positions is always a square number - but what square number? How does it relate to the number of frogs on each side? It seems to be the number of frogs plus one all squared. Putting this algebraically we get (n + 1)2 . So now we can go back to the number of moves. The number of moves is one less than the number of positions so the number of moves with n frogs a side must be (n + 1)2 - 1 . This means that for n = 6, we should get 72 - 1 = 48 . You may wish to check this by returning to the puzzle. |
