This is a question from the book "Thinking Mathematically" by Burton and Mason.
Question: Ten pegs of two colors are laid out in a line of 11 holes as shown below.
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. Find the minimum number of moves necessary to make the change and generalize it to a case where there are $2n+1$ holes.
Related thread: There's an existing thread here that already explains as to why it takes $n^2+2n$ moves to make the change which is something I easily figure out on my own. Please note that in that thread, a peg can move over another peg only if it is of the opposite color whereas the problem in the book does not stipulate that condition. I made the same assumption to arrive at the answer.
The part that I'm stuck with is to show that there can't be any other strategy where it takes less than $n^2+2n$ moves to make the change. Assume for instance that I represent a black peg by 'B', a white peg by 'W', and the hole by 'H'. I assumed that the number of moves involves interchanging 'B' and 'H', and then moving the pegs in only one direction towards the destination. However, how can I show, that it is never possible to have a pattern like 'BBH' changing to a 'HBB' so that the black peg moves by two holes towards its destination? This way, it can further reduce the number of steps needed.
My hunch is that with a pattern like 'HBB', any 'W' stuck to the right of the black pegs will remain there unless the black peg is made to move left, which effectively nullifies the advantage of having moved two steps to the right. However, this explanation is very loose.
- What if there are no white pegs to the left of the black peg in the 'HBB' part of the board?
- More importantly, how can I make it mathematically rigorous that there should never be a pattern like 'HBB' or 'WWH' during the process of transformation assuming the 'B's and 'H's need to be moved further to reach the goal?
My failed approaches and current thought process: Such problems, from my past experience, have a slick solution where some invariant or a monovariant is used to prove the optimality of the algorithm. I tried many but I simply could not go anywhere with it.
Another strategy is the same as that used in the Tower of Hanoi solution, which is an inductive argument, where you show that there's is an algorithm to make the optimal transformation in the $2n+1$ case, by using the optimal transformation in the $2n-1$ case, and there is no way around it. This seems possible as I was able to prove the number of moves needed to make the transformation is $n^2+2n$ using this strategy.
However, it would be simply fantastic to figure out as to why we can never get a pattern like 'HBB' or 'WWH' assuming that both the pegs need to be further moved in order to reach the final goal. I would greatly appreciate it if you can provide the argument for me.