8

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.

TryingHardToBecomeAGoodPrSlvr
  • 1,372
  • The answer in the other thread proves that it takes $n^2+2n$ moves. Isn't that what you want? – Ted May 18 '20 at 04:59
  • @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. – TryingHardToBecomeAGoodPrSlvr May 18 '20 at 05:27
  • I need a rigorous proof as to why a leap of a peg over that of another peg of the same color never occurs. – TryingHardToBecomeAGoodPrSlvr May 18 '20 at 05:30
  • Did you read the section in the answer in the other thread starting with "To make the answer self-contained, here's an explanation of the lower bound." ? – Ted May 18 '20 at 05:54
  • Okay, that paragraph doesn't really seem to prove the lower bound. – Ted May 18 '20 at 05:56
  • There's some confusion here because you made it sound as if the other question addresses the same problem. The other question is about the problem where you're only allowed to jump over pegs of the other colour, so the question that you pose here doesn't arise there. The accepted answer to the other question does prove the lower bound for the different question posed there. – joriki May 18 '20 at 05:59
  • @joriki You are right. Let me make the modifications in my thread. Please do note that I saw this problem originally from the book "Thinking Mathematically" by Mason and Burton, where it does not state that move of one peg over another of the same color is not permitted. – TryingHardToBecomeAGoodPrSlvr May 18 '20 at 06:09
  • 1
    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. – Jaap Scherphuis May 18 '20 at 11:21
  • @JaapScherphuis You are right. I agree with you. It is just that it is a bit unsettling to me having to depend on a verbal argument than a more formal mathematical proof. Please do note that the first part of the proof wherein if you assume that the moves allowed are a one spot slide towards the final position, or a jump between opposite colors again towards the final position, then a perfectly mathematical proof can be given to show that the number of steps needed is $n^2+2n$. – TryingHardToBecomeAGoodPrSlvr May 18 '20 at 11:31
  • However, if we have to show that this is the minimum and a jump between pegs of the same color never occurs, then we have a verbal argument which might be prone to errors. Having a mathematically rigorous proof would have really helped. Since I could not find one, I have posted this question. – TryingHardToBecomeAGoodPrSlvr May 18 '20 at 11:32
  • 1
    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. – Paul Sinclair May 18 '20 at 19:34
  • Does this answer your question: https://math.stackexchange.com/questions/3406631/minimum-number-of-moves-to-change-places-of-blocks/3406646#3406646? – Mike Earnest May 19 '20 at 01:43
  • 1
    @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. – TryingHardToBecomeAGoodPrSlvr May 19 '20 at 05:34
  • There, we need to show that with three pillars and $n$ discs, the minimum number of moves is $2^n-1$. The way it is done is by arguing inductively that the lowest disc has to move, and that in order to move it, you have to put the rest of them into the adjacent pillar in the minimum number of moves for $n-1$ discs, move the lowest disc into the final position (in just one move which is the minimum needed for one disc), and then move the rest to the final pillar again in the minimum number of moves for $n-1$ discs, thereby getting a recursion and the final answer. – TryingHardToBecomeAGoodPrSlvr May 19 '20 at 05:38
  • There is no other way to make that transition, and hence, the minimum number of moves for $n$ discs is $2^n-1$. I was hoping for a similar argument in this problem but it's not that simple. Here, we can consider that a BBBHWWW is same as BXW where X is BBHWW, and then argue that the extreme pegs have to be interchanged just like in tower of Hanoi where the lowest disc has to be moved out. However, it is still not easy in this case to argue that the minimum number of moves necessary is $n^2+2n$. It is kind of mandatory at this point to show that jumps between pegs of same color never occurs. – TryingHardToBecomeAGoodPrSlvr May 19 '20 at 05:42

0 Answers0