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.