Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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?

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/ 
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/