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?

Actually there should be 80 possible positions for the destroyers (not 40), since ships have a bow and a stern and thus have two possible orientations. To my mind, the answer to this problem should be a probability assignment for each of these 80 mutually exclusive and exhaustive positions such that these probabilities total up to 1, and such that the probability of a destroyer being "on" any chosen square is independent of the square chosen. Each of these latter equal probabilities is the sum of the probabilities of all the positions that have one end or the other of a destroyer on the chosen square.  This number of positions differs depending on whether the chosen square is a corner square, an edge square, etc. For the purposes of this problem, one may assume without loss of generality that both orientations of the destroyer are equally likely, which is just the same as ignoring orientation, but the problem still is to specify the probability assignment for the destroyer positions.

Edited on February 16, 2006, 2:04 am

Posted by Richard on 2006-02-15 17:18:41