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?

An even distribution is not possible, because labelling the grid as follows:
A B A B A
B A B A B
A B A B A
B A B A B
A B A B A
We see that there will always be half the ship on A and the other half on B.  So whatever probability distribution you use, the average probability of the B squares will be 1/12, while the average probability for A squares will be 1/13.  Because this is always true regardless of the chosen distribution, and because the distribution we desire doesn't fit this condition, it doesn't exist.
For 1x2 ships, a distribution is possible only for even values of M in MxM grids.  I generalize that for 1xN ships, a distribution is only possible for MxM grids when N|M.

Posted by AvalonXQ on 2006-02-17 05:00:59