ABABA
BABAB
ABABA
BABAB
ABABA
No matter where you put the destroyer in the above 5x5 grid, one A will be covered, and one B will be covered. Therefore, the total probability of finding the destroyer on a B square is 1. But since there are 12 B squares, and each should have a probability of 2/25, the probability should total 24/25, not 1. Therefore, the desired probability distribution is not possible.
In general the probability distribution is possible if and only if M is a multiple of N. If M is a multiple of N, divide the whole grid into a (M/N)^2 squares of NxN size, and place the ship randomly within any of these NxN-sized squares.
If M is not a multiple of N, the probability distribution can be proven impossible in the same way the first case was. For example, take N=4 and M=6.
ABCDAB
BCDABC
CDABCD
DABCDA
ABCDAB
BCDABC
No matter where the 4x1 ship is placed, it covers one A, one B, one C, and one D. There are 9 As, 10 Bs, 9 Cs, and 8 Ds. Each square should have a 1/9 probability of containing part of the ship, but no matter how you split it, some of the D squares will have a higher probability.
Similarly, with any M that is not a multiple of N, you can label the grid with letters such that some letters will be more likely on average to contain part of the ship. |
