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?

The first part is to be interpreted exactly like the second part, where N = 2, and M = 5.

To give a little "motivation" behind the puzzle, imagine you had a computer program that randomly chose a position for your destroyer.  Some positions might be more likely than others.  Suppose you had to show this program to your opponent.  Then, without showing your opponent which position the computer chose, you use the program to place your destroyer.  If the destroyer is more likely to be found in any particular square, that's where your opponent will shoot.

So basically, choose a probability distribution in such a way that you have no weak points. 

Posted by Tristan on 2006-02-15 21:36:39