THE SIX FROGS.
(
Moving Counter Problem)
The six educated frogs in the illustration are trained to reverse their
order, so that their numbers shall read 6, 5, 4, 3, 2, 1, with the blank
square in its present position. They can jump to the next square (if
vacant) or leap over one frog to the next square beyond (if vacant),
just as we move in the game of draughts, and can go backwards or
forwards at pleasure. Can you show how they perform their feat in the
fewest possible moves? It is quite easy, so when you have done it add a
seventh frog to the right and try again. Then add more frogs until you
are able to give the shortest solution for any number. For it can always
be done, with that single vacant square, no matter how many frogs there
are.
Answer:
Move the frogs in the following order: 2, 4, 6, 5, 3, 1 (repeat these
moves in the same order twice more), 2, 4, 6. This is a solution in
twenty-one moves--the fewest possible.
If n, the number of frogs, be even, we require (n squared + n)/2 moves, of
which (n squared - n)/2 will be leaps and n simple moves. If n be odd, we
shall need ((n squared + 3n)/2) - 4 moves, of which (n squared - n)/2 will be leaps
and 2n - 4 simple moves.
In the even cases write, for the moves, all the even numbers in
ascending order and the odd numbers in descending order. This series
must be repeated 1/2n times and followed by the even numbers in
ascending order once only. Thus the solution for 14 frogs will be (2, 4,
6, 8, 10, 12, 14, 13, 11, 9, 7, 5, 3, 1) repeated 7 times and followed
by 2, 4, 6, 8, 10, 12, 14 = 105 moves.
In the odd cases, write the even numbers in ascending order and the odd
numbers in descending order, repeat this series 1/2(n - 1) times, follow
with the even numbers in ascending order (omitting n - 1), the odd
numbers in descending order (omitting 1), and conclude with all the
numbers (odd and even) in their natural order (omitting 1 and n). Thus
for 11 frogs: (2, 4, 6, 8, 10, 11, 9, 7, 5, 3, 1) repeated 5 times, 2,
4, 6, 8, 11, 9, 7, 5, 3, and 2, 3, 4, 5, 6, 7, 8, 9, 10 = 73 moves.
This complete general solution is published here for the first time.
