Library / /116 of 136

, 1997

Combinatorics Difficulty 8.4 Shortlist Prove it Hong Kong

One day, one alien has come to the Earth. Every day, each alien does one of four things, each with a probability of one-fourth: (1) destroying himself, (2) splitting into two aliens, (3) splitting into three aliens, and (4) doing nothing. (A newly created alien also does one of these four things every day starting on the next day, but different aliens do not necessarily do the same thing and act independently.) Find the probability that there is eventually no alien on the Earth.

Solution

The answer is $\sqrt{2}-1$ .
Let $P(n)$ be the probability that there is eventually no alien on the Earth given that there are currently $n$ aliens, where $n$ is a positive integer. Let $P(1) = c$ . Since different aliens act independently, we have $P(n) = c^n$ .
By the given actions, we know that
$P(1) = \frac{1}{4} + \frac{1}{4}P(2) + \frac{1}{4}P(3) + \frac{1}{4}P(1).$
This becomes $4c = 1 + c^2 + c^3 + c$ , which can be factorized as
$(c-1)(c^2+2c-1) = 0.$
Thus, we have $c = 1$ or $-1 \pm \sqrt{2}$ . As $c$ is a probability, we have $0 \le c \le 1$ , so that $c = -1 - \sqrt{2}$ is rejected. We shall also reject $c = 1$ in the following.
Indeed, note that the expected number of aliens arisen from one of the aliens is $\frac{0+2+3+1}{4} = \frac{3}{2} > 1$ . Therefore, the expected number of aliens increases indefinitely. So it is impossible that all aliens must eventually be destroyed. This shows $c < 1$ .
Therefore, the probability is $c = \sqrt{2}-1$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.