2019-04-01
Коротышки, живущие в Цветочном городе, вдруг стали болеть гриппом. В один день несколько коротышек простудились и заболели, и хотя потом уже никто не простужался, здоровые коротышки заболевали, навещая своих больных друзей. Известно, что каждый коротышка болеет гриппом ровно день, причём после этого у него по крайней мере ещё один день есть иммунитет - т. е. он здоров и заболеть опять в этот день не может. Несмотря на эпидемию, каждый здоровый коротышка ежедневно навещает своих больных друзей. Когда началась эпидемия, коротышки забыли о прививках и не делают их. Докажите, что
а) если за день до эпидемии какие-нибудь коротышки сделали прививку и имели в первый день иммунитет, то эпидемия может продолжаться сколь угодно долго;
б) если же в первый день иммунитета ни у кого не было, то эпидемия рано или поздно кончится.
Решение:
а) Эпидемия не кончится, если для трёх друзей $A, B, C$ в первый день у $A$ иммунитет после прививки, $B$ болен, а $C$ здоров.
б) Рассмотрим граф, вершины которого соответствуют коротышкам, а любые два друга соединены рёбрами. Назовём расстоянием между вершинами графа (коротышками) наименьшее количество рёбер в соединяющей их цепочке. Пусть несколько коротышек заболели в первый день (очаг эпидемии). Тогда на следующий день заболеют коротышки, находящиеся на расстоянии 1 от очага, во второй — на расстоянии 2 и только они и т. д. Дело в том, что в $n$-й день у коротышек, находящихся на расстоянии $n — 1$ от очага, иммунитет, и это означает, что волна эпидемии будет распространяться всё дальше от очага, и всё новые и новые коротышки будут заболевать. Но коротышек конечное число. Поэтому в какой-то момент все переболеют по разу и эпидемия закончится.