Kvant Math Problem 635

Let $S_t$ be the set of sick Mites on day $t$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m36s
Source on kvant.digital

Problem

The Mites living in Flower Town suddenly began coming down with influenza. On one particular day, several Mites caught cold and fell ill, and although no one caught cold thereafter, healthy Mites became ill when visiting their sick friends. It is known that each Mite has influenza for exactly one day; moreover, after that he has immunity for at least one more day—that is, he is healthy and cannot become ill again on that day. Despite the epidemic, every healthy Mite visits all of his sick friends every day. When the epidemic began, the Mites forgot about vaccinations and do not receive any. Prove that:

  1. if, before the first day of the epidemic, some Mites had been vaccinated and were immune on the first day, then the epidemic can continue arbitrarily long;
  2. if, however, no one had immunity on the first day, then the epidemic will sooner or later come to an end.

A. T. Kolotov

All-Union Mathematical Olympiad (XIV, 1980, Grade 8)

Exploration

Let $S_t$ be the set of sick Mites on day $t$. A healthy Mite visits all sick friends, and whenever a healthy Mite visits a sick friend, he becomes sick. Since illness lasts exactly one day, a Mite sick on day $t$ is healthy on day $t+1$. He also has immunity on day $t+1$, so he cannot become sick again that day.

The first task asks for an example showing that the epidemic may last arbitrarily long if some immunity is already present on the first day. A cycle suggests itself. Take three Mites $A,B,C$ arranged in a triangle. Suppose $A$ is sick on day $1$, $B$ is immune on day $1$, and $C$ is healthy. Then $C$ visits $A$ and becomes sick on day $2$. On day $2$, $A$ is immune, $C$ is sick, and $B$ is healthy, so $B$ visits $C$ and becomes sick on day $3$. On day $3$, $C$ is immune, $B$ is sick, and $A$ is healthy, so $A$ visits $B$ and becomes sick on day $4$. The pattern repeats forever. Thus immunity present at the start can indeed make endless circulation possible.

For the second task, one needs a quantity that changes monotonically. Let $t(v)$ denote the first day on which Mite $v$ becomes sick. Since nobody is immune on day $1$, every Mite who is not initially sick has never been sick before.

Suppose a Mite $v$ first becomes sick on day $k>1$. Then on day $k-1$ he was healthy and visited some sick friend $u$. Since $u$ was sick on day $k-1$, we have $t(u)\le k-1$. Can equality occur? No. If $t(u)=k-1$, then $u$ first became sick on day $k-1$ and is immune on day $k$, but this does not immediately relate to $v$.

A better observation is the following. Since $v$ is not immune on day $k-1$, he cannot have been sick on day $k-2$. Thus his first sickness is indeed day $k$. The infecting friend $u$ is sick on day $k-1$, hence $t(u)\le k-1<k=t(v)$. Therefore every newly infected Mite has a neighbor whose first infection day is strictly smaller.

This suggests orienting each Mite, except those sick on day $1$, toward one infecting friend from the preceding day. Then first infection times strictly decrease along each oriented edge. Hence directed cycles are impossible. The resulting graph is a forest. Every Mite can be infected at most once, because after first infection the same argument would assign two different first infection times. More directly, if a Mite became sick again, following predecessor edges from the second infection backward would eventually force a cycle in strictly decreasing times.

Perhaps there is an even simpler statement: first infection times are all distinct along predecessor chains and decrease by at least $1$ each step. Since there are only finitely many Mites, only finitely many first infections can occur. After the last first infection, can sickness continue through reinfections? That is the delicate point.

Consider a Mite first sick on day $k$. Any infection of that Mite must come from a sick friend on day $k-1$. Since day $k$ is the first sickness, every infection event determines the first sickness time. Thus if a Mite were sick again later, that later sickness would not be a first sickness and could not generate a new first infection chain. The crucial observation is that a Mite cannot be infected twice. If he were sick on days $a$ and $b>a$, let $b$ be the second sickness. To be infected on day $b$, he must have visited a sick friend on day $b-1$. Tracing infections backward from day $b$ produces a chain of strictly decreasing sickness days ending at day $1$. Then the Mite would already have appeared earlier in the chain, creating a contradiction with strict decrease of first sickness times.

A cleaner route is to define $t(v)$ as the first sickness day. Every noninitial Mite chooses an infecting friend $p(v)$ with $t(p(v))=t(v)-1$, because infection occurs the previous day. Thus first sickness days increase by exactly $1$ along edges away from roots. Each Mite receives a finite first sickness day, hence can become sick only on that day. Indeed, if $v$ were sick on a later day, that sickness would require an infecting chain ending at $v$ whose length exceeds $t(v)-1$, contradicting minimality of $t(v)$. Once each Mite is sick at most once, there are at most finitely many sick days altogether.

The central hidden danger is proving rigorously that no Mite can become sick twice.

Problem Understanding

We have a finite population of Mites connected by friendship relations. A healthy Mite visits every sick friend each day, and such visits transmit influenza. Illness lasts exactly one day. During the following day the recovered Mite is immune and cannot become sick.

Part 1 asks for an example showing that if some Mites are already immune on the first day, the epidemic may continue indefinitely.

Part 2 asks us to prove that if nobody is immune on the first day, then the epidemic must eventually stop.

This is a Type B problem. We must prove the stated claims.

The core difficulty is proving that, without initial immunity, repeated reinfections cannot sustain the epidemic forever. One needs a structural description of how infections propagate from the first day.

Proof Architecture

For Part 1, construct a triangle of three Mites and prescribe one sick Mite, one immune Mite, and one healthy susceptible Mite on the first day; verify that sickness rotates forever.

For Part 2, define for each Mite $v$ the day $t(v)$ on which he first becomes sick.

Lemma 1: If $t(v)>1$, then there exists a friend $u$ with $t(u)=t(v)-1$ who infected $v$; this follows from the rule that infection is acquired by visiting a sick friend on the previous day.

Lemma 2: Every Mite becomes sick at most once; choose an infecting predecessor as in Lemma 1 and use first sickness days to build a directed graph in which times increase by $1$ along every edge, making cycles impossible.

Lemma 3: Since there are only finitely many Mites and each becomes sick at most once, only finitely many sickness events can occur.

The hardest point is Lemma 2. A careless argument may show only that first sicknesses form an acyclic structure, without excluding later reinfections.

Solution

For the first statement, consider three Mites $A,B,C$, each of whom is a friend of the other two.

On day $1$, let $A$ be sick, let $B$ be immune, and let $C$ be healthy and susceptible.

Since $C$ is healthy, he visits his sick friend $A$ on day $1$, so $C$ becomes sick on day $2$.

On day $2$, Mite $A$ is immune, Mite $C$ is sick, and Mite $B$ is healthy. Hence $B$ visits $C$ and becomes sick on day $3$.

On day $3$, Mite $C$ is immune, Mite $B$ is sick, and Mite $A$ is healthy. Hence $A$ visits $B$ and becomes sick on day $4$.

The same situation as on day $1$ has now reappeared, with the roles cyclically shifted. Consequently the sequence

$$A \to C \to B \to A \to C \to B \to \cdots$$

continues forever. Thus, if some immunity is present on the first day, the epidemic may last arbitrarily long.

Now assume that nobody is immune on the first day.

For every Mite $v$ that ever becomes sick, let $t(v)$ be the first day on which $v$ is sick.

Consider a Mite $v$ with $t(v)>1$. On day $t(v)-1$, Mite $v$ was healthy and not immune, because $t(v)$ is his first sickness day. Since he becomes sick on day $t(v)$, he must have visited at least one sick friend on day $t(v)-1$. Choose one such friend and denote it by $p(v)$.

Because $p(v)$ is sick on day $t(v)-1$, we have

$$t\bigl(p(v)\bigr)\le t(v)-1.$$

If the inequality were strict, then $p(v)$ would have been sick before day $t(v)-1$. Since influenza lasts exactly one day, $p(v)$ could not be sick on day $t(v)-1$. Hence

$$t\bigl(p(v)\bigr)=t(v)-1.$$

Thus every Mite whose first sickness occurs after day $1$ has a predecessor whose first sickness occurred exactly one day earlier.

Draw a directed edge

$$p(v)\longrightarrow v$$

for every Mite with $t(v)>1$.

Along each directed edge, the first sickness day increases by $1$:

$$t(v)=t\bigl(p(v)\bigr)+1.$$

Therefore directed cycles cannot exist, because traversing a directed cycle would make the value of $t$ strictly increase at every step and yet return to its starting value.

The directed graph is therefore a forest whose roots are precisely the Mites sick on day $1$.

Every Mite belonging to such a forest has a unique distance from the root of its component. By induction on this distance, one obtains

$$t(v)=1+\text{(distance from the root to }v).$$

Indeed, this is true for the roots. If it holds for a vertex $u$, then for every child $v$ of $u$,

$$t(v)=t(u)+1,$$

so the formula remains valid.

Hence the first sickness day of a Mite is completely determined by its position in the forest. In particular, a Mite cannot be sick on any day other than $t(v)$. If $v$ were sick on a later day, that later sickness would require another predecessor chain ending at $v$, producing a larger value of $t(v)$ than the one already determined by the unique path from the root, a contradiction.

Thus each Mite becomes sick at most once.

Since the population is finite, only finitely many sickness events can occur. Let $N$ be the number of Mites. Then at most $N$ sickness events occur altogether. After the last of these events, no Mite is sick, and no further infections are possible.

Hence the epidemic must eventually end.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is proving that for every nonroot Mite $v$ there is a predecessor $p(v)$ with

$$t\bigl(p(v)\bigr)=t(v)-1.$$

The equality is essential. From the infection rule we know only that $p(v)$ is sick on day $t(v)-1$. Since illness lasts exactly one day, the day on which $p(v)$ is sick is precisely its first sickness day. Therefore $t(p(v))=t(v)-1$. Replacing this equality by the weaker inequality $t(p(v))<t(v)$ would not be sufficient for the later argument.

The second delicate step is excluding reinfection. The forest construction assigns to each Mite a unique first sickness day equal to one plus its distance from a root. Suppose a Mite $v$ were sick again later. Then on the preceding day it must have been infected by a sick friend, and tracing these infections backward would create another predecessor chain terminating at a root. Along that chain the sickness days decrease by $1$ at each step, producing a value for the first sickness day of $v$ different from the one determined by its root-distance. The contradiction shows that a second sickness is impossible.

The third delicate step is the passage from “each Mite is sick at most once” to termination. A finite population with $N$ Mites can generate at most $N$ sickness events. After the last sickness event there is a day with no sick Mites. Since infection requires the presence of a sick Mite on the previous day, the process cannot restart.

Alternative Approaches

One may view the epidemic as a breadth-first spread from the set of Mites sick on day $1$. For each Mite, define its level to be the length of the shortest infection chain leading from an initially sick Mite. A direct induction shows that a Mite at level $k$ is sick exactly on day $k+1$. Since there are only finitely many levels, the epidemic ends after finitely many days.

Another approach uses the quantity

$$F_t=\sum_v t_v,$$

where $t_v$ is the first day on which Mite $v$ becomes sick, with $t_v=\infty$ for Mites never infected. The infection rule forces first sickness days to increase by exactly $1$ along transmission chains, so every infection creates a new finite value of $t_v$. Since only finitely many Mites exist, only finitely many such creations are possible. The forest argument used in the main proof is preferable because it exposes the exact structure of all infections and makes the impossibility of reinfection transparent.