Associated Topics || Dr. Math Home || Search Dr. Math

### 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?

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/
```
Associated Topics:
High School Permutations and Combinations
High School Puzzles
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search