Competition problem — Combinatorics

Library / /119 of 196

Combinatorics Difficulty 5.4 AIME, harder Prove it Soviet Union

Problem:

There is a flu epidemic in elf city. The course of the disease is always the same. An elf is infected one day, he is sick the next, recovered and immune the third, recovered but not immune thereafter. Every day every elf who is not sick visits all his sick friends. If he is not immune he is sure to catch flu if he visits a sick elf. On day 1 no one is immune and one or more elves are infected from some external source. Thereafter there is no further external infection and the epidemic spreads as described above. Show that it is sure to die out (irrespective of the number of elves, the number of friends each has, and the number infected on day 1). Show that if one or more elves is immune on day 1, then it is possible for the epidemic to continue indefinitely.

Solution

Solution:

This is curiously easy. Write $S$ for sick, $N$ for not sick and not immune, and $I$ for immune. Suppose group $A$ are $S$ on day 1 and group $B$ are $N$ on day 1. Then on day 2, $B$ are $S$ , and $A$ are $I$ . So on day 3 no one is sick, $A$ are $N$ and $B$ are $I$ . Thereafter no one can get sick, so the epidemic has died out.

Suppose on day 1, there is also group $C$ who are $I$ . Then on day 2, $B$ are $S$ , $A$ are $I$ and $C$ are $N$ . So on day 3, $C$ are $S$ , $A$ are $N$ and $B$ are $I$ . On day 4, $A$ are $S$ , $B$ are $N$ and $C$ are $I$ , the same as day 1, so the epidemic continues indefinitely.

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.