I am looking at this Frogs game.
For example when $f=5$ the minimum number of moves is $f^2-2f=35$
Also just a note, I am only looking at when the number of red frogs is the same as the number of blue frogs. I wanted an explanation as to why the number of moves is $f^2-2f$. I know I could create a table of values for $f=1,2,3,....$ and then create an equation from that but is there any other way to determine this formula?
On
Sorry, but as a mathematician I have to keep this general, so let's not suppose we have as many red and blue frogs, but let's say you have $m$ red frogs and $n$ blue frogs.
If you compare the distance of each frog from their starting location and their goal location, you'll find that each of the red frogs is $n+1$ spots away from where they should be, and each of the blue frogs is $m+1$ spots away from their target/end location. So, the total distance that needs to be covered is $m\cdot (n+1) + n \cdot (m+1) = 2mn+m+n$
Now, each move in the game is either a jump of a frog over some other frog, or a hop where a frog simply move to an adjacent empty spot.
Note that for each red-blue pair of frogs: they have to swap places at some point in the game, whether the red frog hops over the blue, or vice versa. So, that means you need at least $m\cdot n$ jumps.
Each jump decreases the total distance from current state to goal state by $2$. So, this leaves a distance of $2mn+m+n-2mn=m+n$ to be covered by hops. Since each hop decreases the distance by only $1$, you therefore need at least $m+n$ hops.
In total, then, you need to make at least $mn+m+n$ moves to complete the game. In the case where $m=n$, you thus get $n^2+2n$ moves. (rather than your $n^2-2n$ .. that's wrong!)
Now, you may wonder why red frogs wouldn't be jumping over red frogs in order to get a smaller number of moves (because, again, jumps decrease the distance by $2$, and hops merely by $1$. However, imagine a situation where a red frog jumps over a red frog. In order for this to be an improvement on the current minimum, this means that the red frog jumps from left to right, meaning that you will end up with two red frogs next to each other, and with a gap to their left. Thus, in order for any blue frogs that are left to the right of those frogs to pass these two frogs, the left frog will have to hop left in order to create a space between them. But that means that in effect we have used two moves to get to a position we could have ended up in by simply making the original right frog to the right. And if there are no more blue frogs to the right of these two frogs, then the only way to get into this situation is if either you moved away from the target situation (which means you are wasting moves) or else you must have repeated a situation, and again that means you wasted moves. In all cases, therefore, it never pays to have a frog jump a frog of the same color.
Finally, how do we know that we can finish the game in $mn+m+n$ moves? That is, while the above argument shows that we need to take at least that many moves, is there a guarantee that we can finish it in exactly that many moves?
Well, here is an algorithm that will always work:
Start with the front red frog and have it make a hop.
Now have the first blue frog jump the front red frog, and make the second blue frog make a hop.
Now have the front two red frogs jump, and have the third make a hop.
... OK, you see the pattern: you keep switching between having a bunch of red frogs move, and a bunch of blue frogs move, and you keep increasing the number of frogs from this bunch by 1: 1 red frog, 2 blue frogs, 3 red frogs, etc. And if you sketch this out, you will find that all these moves are indeed perfectly possible (you can always use induction for a rigorous mathematical argument.
Now, you keep doing this until you run out of frogs from one color. At that point, those frogs are all alternating with frogs of the other color, and you can now move that 'alternating' all the way train through, again by having the frogs move in bunches.
Finally, when the train of one color is through, you reach the 'end game', which is pretty much the opposite of the 'start game'.
Again, not easy to make hard mathematically (you'll need to find a clever description that allows for a proof by induction), but once you see the pattern, it is immediately obvious that this always works. Indeed, if you play the applet: first click on the front red frog, then on the first two blue frogs, then the first 3 red frogs, etc: The pattern becomes immediately obvious.
Therefore, you can always finish the game in exactly $mn+m+n$ moves, and not finish it in any less.
Let $a_n$ denote the number of moves to exchange $2n$ frogs. Then, flipping $2(n+1)$ frogs must
Hence, $$a_{n+1} = a_n + 2n - 1$$ with $a_1=1$.
Solving the recurrence yields $a_n = n^2-2n$ as you claim.