n white markers are placed on the first n squares of a row of 2n+1 squares.
There is a space of 1 square and then n black markers.
White markers can only move right.
Black markers can only move left.
Markers can move forward one square, or can jump over a marker of either colour if there is an empty square to land on.
Markers are not removed from the board if jumped.
You DO NOT have to alternate moving black and white markers.

a) Find an algorithm to solve this puzzle.
b) How many moves does it take to complete?
c) If you make random moves what is the probability of completion?

Call a move by a white marker W and by a black marker B.  There is no need to differentiate which white or black marker we are talking about, as on each move there will be at most one of each color that can be moved. 

(Given the condition that a marker can jump over another marker of the same color, technically more possibilities exist.  However, it is never advantageous for a marker to jump over another of the same color, so for the purposes of the following description I will never use that move). 

A) Alternate moving colors, increasing the number of moves by one each time until you reach n.  Still alternating colors, make n moves three times, then decrease back to one.  I know that sounds confusing, so here are some examples (the "make n moves thee times" part has been underlined to clarify what I mean):

For n = 2, move W BB WW BB W

For n = 3, move W BB WWW BBB WWW BB W

For n = 4, move W BB WWW BBBB WWWW BBBB WWW BB W

etc.

B) By observation, each of these puzzles takes n^2 + 2n moves to complete. 

Notice that the number of moves in each game is 1 2 3 ... n n n ... 3 2 1.  The sum of the moves for any n is then 2 times the nth triangle number, plus n.  The formula for the nth triangle number is n(n+1)/2.  Multiplying this by two and adding n gives n(n+1) + n, which simplifies to n(n+2) or n^2 + 2n.

C) I haven't done this yet. :)

Posted by tomarken on 2006-05-30 12:15:31