# The frog game

Finding patterns

The frog game is a puzzle that traditionally has three red frogs, three green frogs and seven lily pads. The red frogs all start on the left-hand lily pads and the green frogs all start on the right-hand lily pads, but they're not happy where they are and they want to swap places. They can move, but only under the following limitations:

• Frogs are stubborn and can only move forward.

• A frog may take a short hop onto the lily pad immediately in front of it.

• A from may jump over one other frog (of any colour) as long as the lily pad where it will land is free.
A very simple game with only two frogs and three lily pads is shown below to illustrate the moves. The game below has three red frogs, three green frogs and seven lily pads. Can you swap the frogs?

Playing the game is fun but there's also some mathematics to be drawn from it. An obvious question is "What is the minimum number of moves it takes to swap the frogs?". An analysis can be made by breaking the moves down into the two possible ones that can be made: a short hop and a jump. For the example game with two frogs and three lily pads the game is solved with two short hops and one jump. You can build on this by gradually increasing the number of frogs, for example two red and two green frogs: It is also useful to consider a non-equal number of red and green frogs: Let the number of red frogs be $$r$$ and the number of green frogs be $$g$$. It can be shown that the total number of short hops, $$h$$ and the total number of jumps, $$j$$, are given by \begin{aligned} h &=r+g, \\ j &= r \times g, \end{aligned} so that the total number of moves required, $$M$$, is $$M = (r+g)+(r \times g).$$