Задача про распространение компьютерного вируса

[recs]

Есть сеть из 20 компьютеров, один из них заражен вирусом. По условиям лицензии на антивирус за один день можно проверить только один компьютер. Каждую ночь вирус перемещается на компьютер адрес которого отличается на единицу (с 192.168.1.5 может переместится на 192.168.1.4 или 192.168.1.6). Всего адреса в сети : с 192.168.1.1 по 192.168.1.20. Найти алгоритм позволяющий обнаружить вирус со вероятностью 1. Проверять несколько компьютеров за один день нельзя, работать ночью тоже.

[drobin]

Предположим, что вирус был в на нечетном компе.
Проверяем комп 1. Вирус либо умирает, либо перемещается на комп с четным номером: 2, 4, ... 20.
Проверяем комп 2. В живых мог остаться только вирус, бывший на 4, 6, .. 20. Он перемещается на номер 3, 5, .. 19.
Проверяем комп 3. В живых мог остаться только вирус, бывший на 5, 7, .. 19. Он перемещается на номер 4, 6, .. 20.
...
Возможный ареал вируса сужается, так его можно прижать к стенке, а затем повторить то же самое, но в предположении, что вирус был на четном компьютере (например, провести операцию с конца).

[Smith]

..если долго сидеть на одном месте, можно увидеть, как мимо пронесут тело твоего врага (с)Народная мудрость

По сути задачи: вирус, теоретически,  может зациклиться и перемещаться между двумя (тремя и т.д.) компьютерами постоянно, не попадая в один из двадцати? если нет, тогда см. "народную мудрость".. т.е. проверяй один и тот же компьютер... если тебе не везет (а тебе не везет), то максимум 20 проверок соответственно

[drobin]

вирус, теоретически,  может зациклиться и перемещаться между двумя (тремя и т.д.) компьютерами постоянно, не попадая в один из двадцати?

Конечно же, да. В условии движения вируса ограничены только тем, что он каждый день передвигается на соседний.

[Smith]

правильное решение было выложено в посте drobin с маленькой поправкой, что если вирус в нечетных не пойман, тогда в последнем (20-ом) компе нужно проверить дважды, чтобы уровнять ходы и повторить последовательную проверку с конца.
спасибо, было интересно!