Kvant Math Problem 101

Consider small initial colony sizes to understand the dynamics.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m01s
Source on kvant.digital

Problem

A single virus enters a colony consisting of $n$ bacteria. During the first minute, it destroys one bacterium, then divides into two new viruses, and simultaneously each of the remaining bacteria also divides into two new bacteria. During the next minute, the two newly formed viruses destroy two bacteria, and then both viruses and all the remaining bacteria divide again, and so on. Will this colony live forever, or will it eventually die out?

R. M. Kovtun

Exploration

Consider small initial colony sizes to understand the dynamics. If $n=1$, the single virus kills the only bacterium in the first minute. After this, there are no bacteria to divide, so the virus population doubles unchecked but has no further effect. If $n=2$, the first virus kills one bacterium, leaving one, which doubles to two. The virus also doubles to two. In the next minute, the two viruses destroy two bacteria, which is exactly the total, leaving none; both populations then double. For $n=3$, the first virus kills one bacterium, leaving two, which double to four. The virus doubles to two. In the next minute, the two viruses kill two bacteria, leaving two, which double to four again. The viruses double to four. Continuing, the virus population grows faster than the bacteria, so the bacteria are eventually overwhelmed. Testing these small cases suggests that regardless of the initial number $n$, the virus population eventually exceeds the bacterial population, leading to the extinction of the colony. The critical insight is that the virus population doubles after killing a number of bacteria equal to its current size, while the bacteria double after being reduced, so the viruses eventually outpace them.

Problem Understanding

The problem describes a discrete-time dynamical system involving a single virus and $n$ bacteria, with both populations doubling each minute under specific interaction rules. The question asks whether the bacterial population survives indefinitely or eventually dies out. This is a Type B problem, "Prove that [statement]". The core difficulty lies in comparing two exponential processes with different offsets: the viruses double after killing bacteria, and the bacteria double after losing some individuals. The key is determining whether there exists a finite time when the virus population equals or exceeds the remaining bacteria, which would result in extinction.

Proof Architecture

The proof will proceed in the following steps. First, define sequences $V_k$ and $B_k$ representing the number of viruses and bacteria at the beginning of the $k$-th minute. Second, derive recurrence relations: $V_0 = 1$, $B_0 = n$, $V_{k+1} = 2 V_k$, $B_{k+1} = 2(B_k - V_k)$, and prove that these formulas correctly model the process. Third, establish that for all $k$, $B_k$ remains non-negative until the first $k$ such that $V_k \ge B_k$, which corresponds to bacterial extinction. Fourth, show that the ratio $B_k / V_k$ eventually drops below $1$ for all $n \ge 1$, implying that the virus population overtakes the bacteria. The hardest step is rigorously proving that $B_k / V_k$ decreases to below $1$, and this is where careless estimation could fail. This requires precise handling of the recurrence rather than intuitive growth comparisons.

Solution

Let $V_k$ denote the number of viruses at the beginning of the $k$-th minute and $B_k$ the number of bacteria at the beginning of the $k$-th minute. Initially, $V_0 = 1$ and $B_0 = n$. According to the problem, each minute proceeds in two stages: the viruses destroy an equal number of bacteria, and then both populations double. After the viruses act, the bacterial population is $B_k - V_k$, which is non-negative as long as $B_k \ge V_k$. Then both populations double, so the recurrence relations are

$V_{k+1} = 2 V_k,$

$B_{k+1} = 2(B_k - V_k).$

We verify these recurrences by induction on $k$. For $k=0$, the first minute, $V_1 = 2 \cdot 1 = 2$ and $B_1 = 2(n - 1)$, which matches the problem statement. Assume the relations hold for some $k \ge 0$. At the $(k+1)$-th minute, the current virus population $V_{k+1}$ kills $V_{k+1}$ bacteria, leaving $B_{k+1} - V_{k+1} = 2(B_k - V_k) - 2 V_k = 2(B_k - 2 V_k)$, which is consistent with iterating the formula. By induction, the relations are correct.

Define the ratio $r_k = B_k / V_k$. Then

$r_0 = n, \quad r_{k+1} = \frac{B_{k+1}}{V_{k+1}} = \frac{2(B_k - V_k)}{2 V_k} = \frac{B_k}{V_k} - 1 = r_k - 1.$

Thus, $r_k$ decreases by $1$ at each step. This sequence is arithmetic: $r_k = n - k$. Consequently, there exists a finite $k_0 = n$ such that $r_{k_0} = 0$, meaning $B_{k_0} = 0$. Therefore, the bacterial population becomes zero after $n$ minutes, and after that the viruses double freely without competition. Since this occurs for every initial $n \ge 1$, the colony cannot survive indefinitely.

This completes the proof. ∎

Verification of Key Steps

The derivation of the recurrence $B_{k+1} = 2(B_k - V_k)$ is delicate because it combines two separate processes: virus destruction and bacterial doubling. To verify, consider $n=3$. Then $B_0 = 3$, $V_0 = 1$, so $B_1 = 2(3 - 1) = 4$, which matches the explicit step-by-step simulation: the virus kills one, leaving two, which double to four. The calculation of the ratio $r_{k+1} = r_k - 1$ is exact, as dividing the recurrence by $V_{k+1} = 2 V_k$ yields $r_{k+1} = (2(B_k - V_k))/(2 V_k) = B_k / V_k - 1$. Testing small $n$ confirms that $r_k$ reaches zero in exactly $n$ steps, validating the extinction argument.

Alternative Approaches

An alternative approach involves writing $B_k$ and $V_k$ explicitly as functions of $n$ and $k$: $V_k = 2^k$ and $B_k = 2^k (n - k)$. This makes extinction evident because $B_n = 2^n (n - n) = 0$. While this direct formula is efficient, deriving it relies on recognizing the arithmetic decrease in the ratio $B_k / V_k$. The main approach using the ratio emphasizes the comparison between the exponential growth rates of the two populations and highlights the underlying mechanism of extinction, making the argument more transparent and generalizable to related processes.