Combinatorial Game Suppose you have $m+n+1$ consecutive squares, and place $m$ white counters in the first $m$ squares and $n$ black counters in the last $n$ squares, leaving a counter-free box in between. White counters can be moved into an open square to the right or over the top of a black square to the right, and black counters can be moved into an open square to the left or over the top of a white square to the left.
Prove the number of steps needed to rearrange all the white counters into the last $m$ squares and all the black counters into the first $n$ squares is $mn+m+n$.
I have tried to prove it using induction, but I'm not sure this can be done, particurarly since there are two variables.
If it possible, please also prove the game can always be completed (I'm not sure how much more difficult this is).
 A: Here I will prove it without using induction.  
For each 'state' consider the number: (number of pairs of white and black squares in which the white one is on the left of the black one) + (number of white squares on the left of the open one) + (number of black squares on the right of the open one)  
This number is initially $mn+m+n$ and finally $0$ and it reduces by $1$ for any step you make.
A: Start by counting each "jump" move as two moves, i.e., think of a move where a white counter jumps over a black counter as simply the white counter first landing on top of the black counter and then moving one more position to the right, and vice versa for black jumping white.  In this setting, all you're doing is moving each white counter $n+1$ positions to the right, and each black counter $m+1$ positions to the left.  (That's because the rules preclude any counter from moving past a counter of the same color.)  So the total number of moves, with jumps counted twice, is simply
$$m(n+1)+n(m+1)=2mn+m+n$$
The only thing to do is subtract the number of extra moves that were introduced for the jumps.  There are $mn$ of them:  Each white counter must encounter each black counter, and one of them must jump the other.  Subtracting it leaves the desired $mn+m+n$.
Added later:  User ajotatxe astutely notes that my initial answer (above) failed to address the OP's request for a proof that the game can always be completed -- that is, that you can avoid getting stuck, with no legal move available, before all the counters are where they need to be.  (One way to get stuck, for example, is to move all the white counters one spot to the right, which leaves the empty square stranded at the far left.)  So let me try to atone for that omission.
It's easy to see that you are in a "bad situation" if you ever have two consecutive white counters anywhere to the right of the empty square with a black counter anywhere to the right of them: those three counters will never be able to move again.  Similarly, you're in a bad situation if you ever have two consecutive black counters to the left of the empty square with a white counter anywhere to the left of them.
So here's the "winning" (solitaire) strategy in a nutshell:

Don't ever make a move that creates a bad situation.

The trick is now to show that if you haven't already created a bad situation, then either the game is complete, or else there is a legal move that doesn't create a bad situation.  You can do this case by case, looking at what's on each side of the empty square.  There are $16$ cases, ranging from BB_BB to WW_WW.  (You need to look two counters on each side, because jumps are allowed.  To avoid having to discuss extra "endpoint" cases, imagine the game starts with a string of white counters pre-positioned to the right of all the black counters and a similar string of black counters to the left of all the whites; these extra counters will never need, or even be able, to move.  Their only role is to simplify the discussion.)
Let me do just a couple of sample cases.  (There is probably some slick way to combine cases, using symmetry or whatnot.  If someone can suggest a simplification, I would appreciate it.)  If you're looking at BB_BB, there is only one legal move to make, namely to BBB_B.  This clearly cannot leave you in a bad situation unless you were already in one.  If you're looking at BW_BB, there are two legal moves, neither of which can create a bad situation.  On the other hand, WB_BB will create a bad situation if you make the (legal but unwise) move to WBB_B, but won't if you do the jump to _BWBB.  And so on down the line.
