Friday, November 20, 2009

The Jumping Frogs Problem

The Jumping Frogs problem is an old pub favourite and someone asked about it on Twitter recently. I cannot remember whether I have ever seen this solution anywhere!


The Jumping Frogs

How many moves does it take for the red frogs (R) and the yellow (Y) frogs to change places?

There is always one empty lily pad. At any time, there is only one frog of each colour that can move to the empty lily pad. If you call out the colour of the frog that is to move, then you will get a sequence of letters R and Y. Now write down the sequence of numbers that shows many times you should call each colour.
Thus 1233321 gives the sequence RYYRRRYYYRRRYYR and this is the sequence for the three frogs problem. The answer is 15 moves. For the two frogs problem the sequence is 12221 which gives RYYRRYYR (8 moves)
For the n frogs problem, by adding the numbers 1,2,3...n...n..3,2,1 and so the number of moves is (n+1) squared -1.

23 comments:

Anonymous said...
This comment has been removed by a blog administrator.
Stephen Morris said...

At the end we want to order them as red frogs, gap, yellow frogs.

Consider each pair of yellow frogs, red frogs and gaps. There are n^2 pairs of yellow frog/ red frog and 2n pairs of frog/gap.

At the start every pair is ordered incorrectly.

Each move we correct one pair. For example if a yellow frog jumps over two red frogs then we gain one from the gap/yellow frog pair, two from the yellow/red frog pairs and lose two from the red frog/gap pairs. This is a net gain of one.

The total number of moves is therefore (n+1)^2 -1 regardless of strategy.

Geoffcobra said...

This is a nice way to count the number of moves in a solution. I think that I have shown how each case can be solved but I am still not sure why this is a unique solution. If you move in any way other than the one that I have described, I don't think that you get a solution.

Stephen Morris said...

My point is that it takes you the same number of moves whatever you do. Each move reduces the number of mis-ordered pairs by one. As there are (n+1)^2 -1 pairs it always takes this number of moves.

An alternative approach would be to shuffle all of the red frogs along one (n moves) then have one yellow frog hop over all of them (one move). Then shuffle all the red frogs along again and have the next yellow frog jump all of them. Keep doing this until all the yellow frogs are correctly placed (n+1)n moves in total. Finally shuffle all the red frogs along so that they are all correctly placed. That gives (n+1)^2 -1 moves in total.

Anonymous said...

Your blog keeps getting better and better! Your older articles are not as good as newer ones you have a lot more creativity and originality now keep it up!

Silverwaver said...

You have provided some elegant ways of counting the number of moves in any possible solution. I believe that I have shown that there a unique solution. If this is correct then we are only really interested in the number of moves in my solution.

Silverwaver said...

Thanks to Anonymous for your encouragement. I hope to keep the blog going this year.

Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...

Nice dispatch and this enter helped me alot in my college assignement. Thanks you for your information.

Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...

interesting article. I would love to follow you on twitter.

Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...

Genial dispatch and this enter helped me alot in my college assignement. Thanks you as your information.

Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...

Nice dispatch and this fill someone in on helped me alot in my college assignement. Thanks you seeking your information.

Anonymous said...

Genial fill someone in on and this fill someone in on helped me alot in my college assignement. Gratefulness you for your information.

Anonymous said...

Approvingly your article helped me truly much in my college assignment. Hats incorrect to you enter, choice look forward for more cognate articles soon as its one of my pet issue to read.

Anonymous said...

Sorry for my bad english. Thank you so much for your good post. Your post helped me in my college assignment, If you can provide me more details please email me.