FreeProbabilityEasy

Ship Destroyer

Asked atCitadel

A $4 \times 4$ grid has a ship in each of its $16$ cells. Four bombs fall, each landing in a cell chosen independently and uniformly at random (two bombs may hit the same cell). A bomb destroys every ship in its row and every ship in its column. What is the probability that all $16$ ships are destroyed?

Solution

Try it yourself first. Open a hint if you get stuck.

Hint 1

A ship survives only if no bomb lands in its row and no bomb lands in its column. When can that happen?

Hint 2

Every ship is destroyed exactly when the four bombs hit all four rows, or all four columns. Count each case and use inclusion–exclusion.

Show solution

When does a ship survive? The ship in row $i$ , column $j$ survives only if no bomb lands in row $i$ and no bomb lands in column $j$ . So some ship survives exactly when there is an empty row and an empty column.

Turning that around, every ship is destroyed exactly when

$R$ : the bombs hit all four rows, or
$C$ : the bombs hit all four columns.

With only four bombs, "hit all four rows" means the bombs land in four different rows.

Count the outcomes. Treat the bombs as ordered; there are $16^4 = 65{,}536$ equally likely outcomes.

$|R|$ : give the four bombs four different rows ( $4! = 24$ ways), then any column each ( $4^4 = 256$ ways): $24 \cdot 256 = 6{,}144$ .
$|C|$ : the same count with rows and columns swapped: $6{,}144$ .
$|R \cap C|$ : four different rows and four different columns: $4! \cdot 4! = 576$ .

By inclusion–exclusion,

|R \cup C| = 6{,}144 + 6{,}144 - 576 = 11{,}712.

Probability.

P = \frac{11{,}712}{65{,}536} = \frac{183}{1024} \approx 0.17871.

Answer: $0.17871$ .

Question

Solution