I am looking into the following problem:
Ten pegs of 2 colors are laid out in a line of 11 holes (5 black to the left, a hole, 5 white to the right). I want to interchange the black and white pegs, but I am only allowed to move pegs into an adjacent empty hole or to jump over one peg into an empty hole. Can I make the interchange?
The configuration is like this (the space is the empty hole):
BBBBB WWWWW
I think I proved it can be done by induction and I wanted to make sure my induction proof is sane.
I start with $B=1$ and $W=1$ (denoting the numbers of black and white pegs).
B W
BW
WB
W B
So it is possible to make the swap for $B=1$ and $W=1$.
I also confirm that this is possible for $B=2$ and $W=2$
BB WW //start
B BWW // move black to the right
BWB W // white jump's to the left
BW BW // move black to the right(inner was reversed)
BWWB // white jump's to the left
BWW B // move black to the right
BW WB // move white to the right (outer right reversed but move backwards)
WBWB // jump black to the right
W BWB // move white to the left
WB WB // move black to the left (outer left reversed)
WBW B // move white to the left
W WBB // jump black to the right
WW BB // move white to the left
Proof:
Base case: For $B=1$ and $W=1$ we can interchange the pegs using only the valid moves.
Inductive hypothesis: I can interchange $B = N$ and $W = N$ pegs using only valid moves
Inductive step:
We have $B = N + 1$ and $W = N + 1$ pegs.
BBBBB...BBB WWW...WWWWW
We can interchange the inner $B=N$ and $B=N$ by inductive assumption. Hence we get:
BWWWW...WWW BBB...BBBBW
I.e. we are left with a misplaced peg (the $nth + 1$) at each side.
But we can move the $nth +1$ towards the center using valid moves as each one is just an application of the base case (subproblems of size $1$).
I.e.
BWWWW...WWW BBB...BBBBW
B WWWW...WWWBBB...BBBBW (all whites moved to the right)
The B W which is at the outer left is just a subinstance of the original problem and can be interchanged
W BWWW...WWWBBB...BBBBW
Now all the whites can continue moving to the left and we do the same (symmetrical) process in the right side as well.
In the last step we end up with
WWWWW...WWB WBB...BBBBB
Those (outer) misplaced pegs is a sub-instance of the original problem of size $1$ and can be interchanged.
Hence we can do the interchange for $B = 5$ and $W = 5$ or in general any number of pegs $B=n$ and $W=n$