0

A board has 2n+ 1 holes in a line, with n red pegs starting in the first n holes, followed by a gap, thenn blue pegs in the remainingn holes. The pegs may be moved either one hole forward into an empty hole or a peg of one color may jump over a peg of the other color into an empty hole on the other side. What is the fewest number of moves it takes to completely interchange the red and blue pegs?

The solution is written here:https://sumo.stanford.edu/old/smt/2007/Advanced%20Topics%20Solutions.pdf

But I can't understand the algorithem can you explain it?

Taha Akbari
  • 3,559
  • Which of those 10 answers are you referring to? Edit: Must be #8. –  Nov 10 '17 at 17:23
  • @tilper number$8$. – Taha Akbari Nov 10 '17 at 17:24
  • "But I can't understand the algorithem can you explain it?" How the heck can anyone explain something you don't understand when you just read a complete explanation? How the heck can we do that if we don't understand why you don't understand. The very least you can do is point out what you don't unnderstand. Otherwise all we can do is paraphrase with no faith you will understand that. If you can't ask a question, you can't expect anyone to be able to answer it. – fleablood Nov 10 '17 at 17:25
  • I suggest you try to follow the algorithm yourself step by step for some small numbers ($n=2$ or $3$ to start with), either by drawing the pegs after each step, or by finding some objects like coins and pens and pretend they are pegs. – Arthur Nov 10 '17 at 17:25
  • Well, I apologize. That is one of the worst written answers I've ever seen. But still point out where specifically you have trouble with it. – fleablood Nov 10 '17 at 17:29
  • @fleablood I can't understand What will happen after doing the first step of algorithem which side is the empty hole? – Taha Akbari Nov 10 '17 at 18:02
  • Draw a picture. Actually, so far as I can tell, this is the only possible course of action at all without ever moving pegs backeards. You can't actually NOT do the algorithm. – fleablood Nov 10 '17 at 18:32

1 Answers1

1

Because I like drawing pictures in Mathematica, here is an illustration of the algorithm for $n=4$.

To count the moves, of course, we don't need to follow the algorithm carefully: all we need to know is that no backwards moves are made, and therefore we achieve the lower bound of $n^2+2n$.

To make the answer self-contained, here's an explanation of the lower bound. Each of $2n$ pegs must move a distance of $n+1$, which is a total distance of $2n(n+1)$. If we moved a distance of $1$ at each step, that would be $2n^2 + 2n$ moves. But there are $n^2$ moves (for each blue-peg-red-peg pair) at which a peg jumps and moves a distance of $2$, so we save $n^2$ moves, and the lower bound is $n^2+2n$.

Starting position

RRRR.BBBB

Step 1: move red peg (1 move)

RRR.RBBBB

Step 2: move blue pegs (2 moves)

RRRBRB.BB

Step 3: move red pegs (3 moves)

R.RBRBRBB

Step 4: move blue pegs (4 moves)

RBRBRBRB.

Step 5: move red pegs (4 moves)

.BRBRBRBR

Step 6: move blue pegs (4 moves)

BBRBRBR.R

Step 7: move red pegs (3 moves)

BB.BRBRRR

Step 8: move blue pegs (2 moves)

BBBBR.RRR

Step 9: move red peg (1 move)

BBBB.RRRR

Misha Lavrov
  • 142,276
  • Here's a question. If we ignore jumping backwards and after we choose a color to go first, is there any OTHER possible outcome but this algorithm? – fleablood Nov 10 '17 at 21:02
  • There's no other complete solution without jumping backward. But we might make mistakes that don't involve jumping backwards at first, but get us stuck later at a place we're forced to jump backwards. So we still need some rule to tell us which peg to move when we have options. – Misha Lavrov Nov 10 '17 at 21:15
  • For example, we could decide to begin by moving all four red pegs forward one space. That would be kind of stupid, and we'd have to undo several of those moves, but it is legal. – Misha Lavrov Nov 10 '17 at 21:16
  • Oh.... I overlooked that. So the answer to my question is "Yes" and my statement "Actually, so far as I can tell, this is the only possible course of action at all without ever moving pegs backeards" was simply incorrect. – fleablood Nov 10 '17 at 23:11
  • It's dumb, but somehow I didn't think we even had options once we moved the red peg except to jump the blue. It didn't occur to me that the red peg behind would actually also have an option. (Of course, if we take it then, if we can't go back, there will only be red options till the end and it will end incomplete) – fleablood Nov 10 '17 at 23:13