# How many moves do I need to solve the leap frog puzzle?

This is a standard puzzle that all of us have seen (and also probably appears in Conway's combinatorial game theory books).

There are $n$ green frogs and $n$ red frogs sitting on $2n+1$ lily pads in the given configuration

GGG_RRR


The frogs can only leap to an empty lilypad. They can jump over at most one frog.

The problem is to change the original configuration to

RRR_GGG


I want to show that this can be done optimally $(n+1)^2 - 1$ steps for each $n$. I tried doing this by trying to find a recurrence on $n$, but I failed.

To get the number of moves, look at how many spaces each frog must move. Each frog moves $n+1$ spaces, so there are a total of $2n(n+1)$ spaces moved. There are $n^2$ jumps where a frog moves two spaces, so the number of moves is $2n(n+1)-n^2=n^2+2n=(n+1)^2-1$
• Why there cannot be more than $n^2$ jumps? – Momo Jan 12 '17 at 16:39
• There are $n$ frogs on each side. Each one jumps over all the frogs of the other color. – Ross Millikan Jan 12 '17 at 16:52