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?

First off, I just realized that the problem doesn't explicitly state the point of this game.  I assumed it was to reverse the positions of the white and black markers, I can't imagine what else it would be!

Anyway...

C) On the first turn (for any size n puzzle) there are 4 legal moves, two of which can lead to a win.

At any other point in the game, there can be as few as 1 and as many as 3 legal moves to make.  Unlike the first move, only one of the legal moves on each subsequent turn will lead to a win. 

The probability of winning by making random moves is then the product of the the probabilities of making the correct move at each turn.  As stated, the probability of making a correct move on the first turn is 2/4.  Any turn that has only one legal move is negligable as the probability of choosing correctly is 1, so we don't have to be concerned with them.

We need to find, then, the number of turns that have 2 and 3 legal moves respectively.

Purely by observation (and I sure hope I counted these right) I found the following:

    | # of turns with...  
  n |  3 L.M.   2 L.M.          
------------------------
  2 |    0        3
  3 |    2        6
  4 |    4        11

L.M. stands for "legal moves".

Using the above chart, the probability of winning by making random moves is then:

For n = 2:  1/2 * 1/3^0 * 1/2^3  = 1/16
For n = 3:  1/2 * 1/3^2 * 1/2^6  = 1/1152
For n = 4:  1/2 * 1/3^4 * 1/2^11 = 1/331776

(The 1/2 at the beginning of each of those comes from the 2/4 probability on the first turn).

I don't immediately see a definite pattern and I don't have time right now to manually count the possibilities for n > 4.  Maybe someone with some programming skills can finish this up faster than I can. :)

Posted by tomarken on 2006-05-30 13:01:48