Frogs Changing Sides

Date: 09/04/2002 at 21:31:10
From: Jean
Subject: Changing sides

There are ten frogs on ten lilypads to the left. There are ten frogs 
on ten lilypads to the right. There is one empty lilypad between them.  

The two groups need to swap places. They are only allowed to move in 
two ways. A frog may jump over a frog next to it, or a frog may move 
onto an empty lilypad next to it. What is the least number of jumps 
needed for all the frogs to trade sides?

I can't figure out how to get started.  Do I put one frog on top of 
the other on the empty lilypad in the middle, or what?

Please help me!
Jean

Date: 09/04/2002 at 23:14:46
From: Doctor Peterson
Subject: Re: Changing sides

Hi, Jean.

You never have to violate the rules, such as by putting two frogs on 
one pad. Just take it one step at a time. You might want to play with 
pennies and dimes or some other kind of marker. I'll use letters for 
the left group and numbers for the right group:

    0 1 2 3 4 5 6 7 8 9 _ a b c d e f g h i j

The first move might be a hop one place into the middle:

    0 1 2 3 4 5 6 7 8 9 _ a b c d e f g h i j
                       \
    0 1 2 3 4 5 6 7 8 _ 9 a b c d e f g h i j

or a jump over another into the middle:

    0 1 2 3 4 5 6 7 8 9 _ a b c d e f g h i j
                     -->
    0 1 2 3 4 5 6 7 _ 9 8 a b c d e f g h i j

Now you can keep on with the same kinds of moves. But in what order?

One good way to solve a puzzle like this is to start with an easier, 
smaller case:

    0 _ a

How can we exchange these?

    0 _ a
     \
    _ 0 a
     <--
    a 0 _
       \
    a _ 0

That took three moves, and you can't get any better.

Try doing it with two on a side, then three, and you should develop a 
strategy that will work for any number, and perhaps discover a pattern 
in the number of moves it takes.

If you have any further questions, feel free to write back.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/