1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

To prove that a frog jumping another of the same color cannot be part of the optimum solution, assume it is a green frog. We then must have GG_ with other frogs in the row. How did we get here? The first G could have jumped backwards, but then jumping forwards undoes the move and we would be better without the pair. An R could have moved backwards, but then the front G should have jumped it and we would be farther along. Finally, a G could have moved forwards, but then we had GG_ before (one space to the right) and we look at the move before that.

$\endgroup$
  • $\begingroup$ Why there cannot be more than $n^2$ jumps? $\endgroup$ – Momo Jan 12 '17 at 16:39
  • $\begingroup$ There are $n$ frogs on each side. Each one jumps over all the frogs of the other color. $\endgroup$ – Ross Millikan Jan 12 '17 at 16:52
  • $\begingroup$ I understand that as long as there are frogs of opposite color waiting to pass through, a frog cannot jump over a frog of the same color, as it would create blockage. But why jumping over a frog of the same color can never lead to a solution, even at the end? $\endgroup$ – Momo Jan 12 '17 at 17:21
  • $\begingroup$ If a frog jumps one of the same color, you will have two frogs of one color with the blank behind them. Everything will then be blocked. For example, in the original position, say the red frog jumps. You now have GGGRR_R and the greens can never get past the reds. I have usually seen it that frogs can only move in one direction and can only jump the other color. Without these, you can have longer solutions because you can undo moves. $\endgroup$ – Ross Millikan Jan 12 '17 at 17:28
  • $\begingroup$ What I was trying to ask was why we can't reach a configuration like RRRGGG_, when a jump over the same color and a slide would lead to the solution RRR_GGG. Or if we can reach such a configuration, why it cannot be part of the shortest solution. (It seems to me that your solution, although correct - I already upvoted it - needs a little bit more explanation). $\endgroup$ – Momo Jan 12 '17 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.