Ship Destroyer

Question

Sixteen ships occupy the cells of a $4	imes4$ grid. You have four bombs to drop, each landing independently and uniformly at random in one of the 16 cells (with repetition allowed). Whenever a bomb lands in a particular cell, it destroys every ship in that bomb's row and its column.

What is the probability that, after all four bombs have fallen, every ship on the grid has been destroyed?

QuantSoc · Accepted Answer

Observe that each bomb drop is one of 16 equally likely outcomes, so there are in total $16^4$ possible ordered sequences of four bomb-drops.

To ensure every ship is destroyed, each of the 4 rows must contain at least one bomb **OR** each of the 4 columns must contain at least one bomb. Equivalently, let $E_R$ be the event "the bombs land in four distinct rows," and $E_C$ be the event "the bombs land in four distinct columns."

A ship in row $i$ is wiped out as soon as at least one bomb falls in row $i$, and a ship in column $j$ is wiped out as soon as at least one bomb falls in column $j$. Therefore, all ships are destroyed if and only if at least one of the events $E_R$ or $E_C$ occurs.

To count $|E_R|$, we require the four bombs to occupy four different rows, while columns may repeat. Since bombs are ordered, there are $4! = 24$ ways to choose a distinct row for each bomb. For each bomb, there are 4 possible columns, giving $4^4 = 256$ choices for the column positions. Hence

$$
|E_R|=4!	imes4^4=24	imes256=6,144.
$$

By exactly the same reasoning,

$$
|E_C|=4!	imes4^4=24	imes256=6,144.
$$

Next, $|E_R\cap E_C|$ is the number of sequences in which the bombs occupy four distinct rows and four distinct columns simultaneously, that is, no two bombs share a row or a column.

We first choose a permutation of the four rows for the four bombs, giving $4!$ ways, and independently choose a permutation of the four columns, giving another $4!$ ways. Thus,

$$
|E_R\cap E_C|=4!	imes4!=24	imes24=576.
$$

Finally, by the principle of inclusion-exclusion, the number of bomb-drop sequences that achieve "all ships destroyed" is

$$
|E_R\cup E_C|
=|E_R|+|E_C|-|E_R\cap E_C|
=6,144+6,144-576
=11,712.
$$

Therefore, the desired probability is

$$
\frac{11,712}{16^4}
=\frac{11,712}{65,536}
=\frac{183}{1,024}
\approx0.1787.
$$

Hence, the probability that all ships are destroyed is

$$
\boxed{\frac{183}{1,024}}.
$$