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?

(In reply to A solution by Leming)

I think this is possible if M is a multiple of N.

First, divide the grid up into a M/N by M/N grid of NxN squares.  Now choose an NxN group at random.  Now place the destroyer in the chosen square at random.  It should touch the sides and there will be 2N positions possible.  Not all positions of the destroyer in the MxM are possible but each square has an even chance of being covered.

Posted by bernie on 2006-02-15 17:01:32