6
$\begingroup$

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.

enter image description here

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.

  1. What if there are no white pegs to the left of the black peg in the 'HBB' part of the board?
  2. 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.

$\endgroup$
  • $\begingroup$ The answer in the other thread proves that it takes $n^2+2n$ moves. Isn't that what you want? $\endgroup$ – Ted May 18 at 4:59
  • $\begingroup$ @Ted I was able to prove that we can accomplish the switching of pegs in $n^2+2n$ moves. However, neither the thread nor I could show that this is indeed the least number of moves needed. In the thread above, I have mentioned one way in which the number of moves can be less than $n^2+2n$, the one where a leap of one peg occurs on top of of a peg of the same color (ie a transformation, for example, from 'BBH' to 'HBB'). However, we all have a hunch that such a move can never occur during a successful transformation with least number of moves. $\endgroup$ – TryingHardToBecomeAGoodPrSlvr May 18 at 5:27
  • 1
    $\begingroup$ The important fact is that there is only one empty spot. If you jump one peg forward over a peg of the same colour, and there are pegs of the other colour that still have to come the other way and pass them, then the only way is to make room by doing a backwards move or jump with either peg. This undoes any advantage the same-colour-jump gave. So the only situation where such a jump may help is when there are no pegs of the other colour in front. However, you can only get to that situation by backwards jumps or moves. In either case, there is no advantage to jumping same colour. $\endgroup$ – Jaap Scherphuis May 18 at 11:21
  • 1
    $\begingroup$ The "verbal argument" is a summary of a formal proof. It just needs the details filled in. The only hand-wavy part is "This undoes any advantage the same-colour-jump gave". The rest of it easily translates into a formal proof. So if that one line can be justified, the rest of the proof is straight-forward. $\endgroup$ – Paul Sinclair May 18 at 19:34
  • 1
    $\begingroup$ @MikeEarnest Thanks for pointing me to that thread. I was actually able to get the answer independently. I can't however explain as to why a jump never occurs between pegs of the same color because if that also occurs, then the answer is a number lesser than $n^2+2n$. While we can provide intuitive verbal explanation as to why that is so, it is not rigorous. I need a rigorous mathematical proof that pegs of the same colors never cross over each other as long as they both need to be further moved towards their final destination. An example of a rigorous argument is that of the tower of Hanoi. $\endgroup$ – TryingHardToBecomeAGoodPrSlvr May 19 at 5:34

Your Answer

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

Browse other questions tagged or ask your own question.