You must randomly place a destroyer (a 1x2 sized ship) on a 5x5 grid such that if I searched in any single square, my probability of finding the destroyer there is exactly 2/25. Is such a probability distribution possible? You cannot simply choose randomly one of the 40 possible positions of a destroyer because corners would have a 1/20 chance to contain the destroyer, while the center would have 1/10 chance.

Generalize to a 1xN sized ship in a MxM grid. When is it possible to place the ship with an even probability distribution in each square?

I have found a simple "random" way of doing it for a 5x5 grid with a 1x2 ship. I have yet to see if it will work for a larger grid or bigger ships.
First, create a distribution that balances out the chances of the ship being in a given square. Using recursion in Excel (GO EXCEL!) I found that a checker-board pattern will work.
X 0 X 0 X
0 X 0 X 0
X 0 X 0 X
0 X 0 X 0
X 0 X 0 X

If you place the anchor point of the ship on one of the "X"s (randomly) and then randomly let the ship swing to one of the available directions the probability that the ship will be in each square is as follows:

The probability of an X being full is 1:13. 

The probability of a 0 on the edge being full is one-half of the corner's possibility plus one-third the center edge's possibility plus one-fourth the interiror spots possibility.

P=(1/2 + 1/3 + 1/4)*1/13 = 13/12 * 1/13 = 1/12

The probability of a 0 near the center being full is:

P=(1/4 + 1/4 + 1/4 +1/3)*1/13 = 1/12

This gives:

1/13  1/12  1/13  1/12  1/13
1/12  1/13  1/12  1/13  1/12
1/13  1/12  1/13  1/12  1/13
1/12  1/13  1/12  1/13  1/12
1/13  1/12  1/13  1/12  1/13

Now firing a random shot there is a 13/25 chance of hitting a 1/13 spot or a 12/25 chance in hitting a 1/12 spot. This equals to a 1/25 + 1/25 for a total of 2/25 chance of the ship being hit.

Posted by Leming on 2006-02-15 16:24:16