Условие задачи (1980, № 7) Задача М635 // Квант. — 1980. — № 7. — Стр. 22—23; 1981. — № 4. — Стр. 26—27.
Коротышки, проживающие в Цветочном городе, вдруг стали болеть гриппом. В один день несколько коротышек простудились и заболели, и хотя потом уже никто не простужался, здоровые коротышки заболевали, навещая своих больных друзей. Известно, что каждый коротышка болеет гриппом ровно день, причём после этого у него по крайней мере ещё один день есть иммунитет — т. е. он здоров и заболеть опять в этот день не может. Несмотря на эпидемию, каждый здоровый коротышка ежедневно навещает всех своих больных друзей. Когда началась эпидемия, коротышки забыли о прививках и не делают их. Докажите, что:
- если до первого дня эпидемии какие-нибудь коротышки сделали прививку и имели в первый день иммунитет, то эпидемия может продолжаться сколь угодно долго;
- если же в первый день иммунитета ни у кого не было, то эпидемия рано или поздно кончится.
Изображения страниц
Решение задачи (1981, № 4) Задача М635 // Квант. — 1980. — № 7. — Стр. 22—23; 1981. — № 4. — Стр. 26—27.
Пусть
$A$, $B$, $C$ — три друга, причём$A$ в начале эпидемии имел иммунитет,$B$ заболел в первый день, а$C$ был здоров, но иммунитета не имел.Если предположить, что иммунитет у каждого из этих коротышек длится один день, то, учитывая правила поведения коротышек, получаем «график заболеваемости», изображённый на рисунке («И» — имеет иммунитет; «З» — здоров, но не имеет иммунитета; «Б» — болен). Очевидно, в такой ситуации эпидемия никогда не закончится. $$ \begin{array}{|c|c|c|c|} \hline \text{День}&A&B&C\\\hline 1&\text{И}&\text{Б}&\text{З}\\\hline 2&\text{З}&\text{И}&\text{Б}\\\hline 3&\text{Б}&\text{З}&\text{И}\\\hline 4&\text{И}&\text{Б}&\text{З}\\\hline 5&\text{З}&\text{И}&\text{Б}\\\hline \vdots&\vdots&\vdots&\vdots\\ \end{array} $$
Приведём два решения этой задачи.
Первое решение наиболее ясно показывает, как идёт распространение эпидемии. Изобразим всех коротышек точками и соединим линиями тех из них, которые знакомы между собой. Будем говорить, что коротышка
$B$ удалён от коротышки$A$ на расстояние$k$, если от коротышки$A$ можно перейти к коротышке$B$, пройдя по$k$ линиям, и нельзя перейти по меньшему числу линий. Разобьём множество всех коротышек на подмножества$M_0$, $M_1$, $M_2$, $\ldots$ по следующим правилам: в множество$M_0$ входят все коротышки, заболевшие в первый день эпидемии; в множество$M_1$ — все коротышки, удалённые от коротышек из$M_0$, на расстояние 1; в множество$M_2$ — все коротышки, удалённые от коротышек из$M_0$ на расстояние 2, и т. д. Коротышек, которые вообще не связаны с коротышками из$M_0$ никакой цепочкой знакомств, включим в отдельное множество$M'$ — эти коротышки никогда не заболеют. Поскольку общее число коротышек конечно, число множеств$M_k$ тоже конечно. С другой стороны, из определения расстояния между коротышками следует, что коротышка из множества$M_k$ заболеет ровно на($k+1$) -й день эпидемии, причём может передать болезнь только коротышкам из множества$M_{k+1}$ (остальные его знакомые принадлежат множеству$M_{k-1}$ и на($k+1$) -й день имеют иммунитет). Следовательно, в первый день болеют только коротышки из множества$M_0$, во 2-й — только коротышки из$M_1$ в 3-й — только коротышки из$M_2$ и т. д. Так как число множеств$M_k$ конечно, эпидемия рано или поздно закончится.Второе решение — от противного.
Если каждый коротышка будет болеть ровно один раз, то эпидемия кончится. Если же она не кончится, то должен быть коротышка, заболевший второй раз. Пусть в
$k$ -й день коротышка$A$ заболел во второй раз первым (или одним из первых, если в этот же день повторно заболело несколько человек). Он заразился накануне от своего друга$B$, а$B$ болел при этом в первый раз, заразившись в($k-2$) -й день. Так как$A$ и$B$ — друзья,$B$ должен был заразиться от$A$, когда$A$ болел в первый раз. Следовательно,$A$ болел впервые в($k-2$) -й день, а на следующий день имел иммунитет и поэтому не мог заразиться. Мы пришли к противоречию, показывающему, что никакой коротышка не мог болеть дважды.