www.treasuremaze.com

Random Leaps

Management has deemed it appropriate to give the astute treasure seeker this brief treatise on the math behind the "random leap".

If a given maze has n cells, the chances of leaping to a given cell d, d moves from the target, are given by this simple equation:

1/n² + ((²₁) * (1/n)*(d/n)) = 1/n² + (2*d/n²) 

                              = (1+(2*d))/n²

^{Consider the simplified 4 X 4 maze below:}

From the formula above the probability of randomly leaping into the treasure cell (15), is expressed :

(1+(2*d))/n² = (1+(2*0))/256

             = 1/256

               = 0.00390625

The probability of leaping into cell (8) is: 

(1+(2*d))/n² = (1 + (2*8))/256 = 0.06640625

Of leaping to cell (0):

(1 + (2*d))/n² = (1 + (2*15)/256 = 0.12109375

 The probability of leaping into any one of several cells within d moves from the treasure could be expressed as the sum of probabilities:

{(1+(2*0))/n²}+{(1+(2*1))/n²}+{(1+(2*2))/n²}+..

                                    ..+{(1+(2*d))/n²}

Reducing to

(1 + 3 + 5 +..+(1+2d))/n²

Then to

(d + 2 + 4 + 6 +..+2d)/n²

(d + 2*(1+2+3+..+d))/n²

Then using Gauss's little theorem for the sum of consecutive digits:

(d+1+ 2*((d+1)*d/2))/n² = (d²+2*d+1)/n²

So the probability of leaping to within 4 cells of the treasure is computed as:

(16+8+1)/256 = 0.09765625

to within 8 cells:

(64+16+1)/256 = 0.31640625

to within 12 cells:

(144+24+1)/256 = 0.66015625

to within 15 cells:

(225+30+1)/256= 1.0  (That's anywhere in the maze, duh!)

Treasure maze #1 was a 64X64 maze, containing 4096 cells, of which 1/4th were void. The probability of making a random leap to within 200 cells of the treasure is left as an exercise.