|
|
 |
Условие
Компьютеры 1, 2, 3, ..., 100 соединены в кольцо (первый со вторым, второй с третьим, ..., сотый с первым). Хакеры подготовили 100 вирусов, занумеровали их и в различное время в произвольном порядке запускают каждый вирус на компьютер, имеющий тот же номер. Если вирус попадает на незаражённый компьютер, то он заражает его и переходит на следующий в цепи компьютер с большим номером до тех пор, пока не попадёт на уже заражённый компьютер (с компьютера 100 вирус переходит на компьютер 1). Тогда вирус погибает, а этот компьютер восстанавливается. Ни на один компьютер два вируса одновременно не попадают. Сколько компьютеров будет заражено в результате атаки этих 100 вирусов?
Решение
Докажем несколько утверждений.
1) На каждый компьютер вирусы попадают хотя бы дважды.
Рассмотрим, например, компьютер 1. Если на него первым попал вирус с компьютера 100, то на него попадет ещё и вирус 1. Если же первым на компьютер 1 попал вирус 1, то вирус, попавший на компьютер 100 первым (возможно, это тот же вирус 1, обошедший весь круг), обязательно перейдёт на компьютер 1.
2) Все вирусы погибнут.
Действительно, на каждый компьютер попадает хотя бы два вируса, при этом второй вирус по условию погибает. Значит, на каждом компьютере погибнет хотя бы один вирус. Но вирусов столько же, сколько компьютеров, значит, все вирусы погибнут.
3) Ни на один компьютер не могут попасть три вируса.
Рассмотрим компьютер, на котором погиб последний из всех 100 вирусов (пусть это компьютер 1; если несколько последних погибли одновременно, рассмотрим любой из них). Тогда этот вирус попал на на него вторым (иначе на нём погибло бы больше одного вируса), и позже вирусы на него уже не попадали. Таким образом, на компьютер 1 попали ровно два вируса. Но тогда и на компьютер 2 попали ровно два вируса: один "свой" и один с компьютера 1. Тогда и на компьютер 3 попало ровно два вируса. И т. д.
Итак, на каждый компьютер вирусы попадают ровно два раза, а после этого компьютер восстанавливается. Таким образом, после гибели всех вирусов все компьютеры будут работать нормально!
Ответ
Заражённых компьютеров не будет.
Замечания
Эта задача – переформулировка задачи, предлагавшейся в 2001 г. на V Кубке им. Колмогорова.
