|
|
 |
Условие
Страна Фарра расположена на 1 000 000 000 островов. Между некоторыми островами каждый день курсируют пароходы. Маршруты пароходов устроены так, что с каждого острова можно попасть на любой другой (возможно, за несколько дней). Шпион и майор Пронин могут совершать не более одного рейса в день на пароходе и не имеют никакой другой возможности попасть с острова на остров. Шпион не ездит на пароходе 13 числа каждого месяца, майор Пронин не суеверен и всегда знает, где находится шпион. Доказать, что майор сможет поймать шпиона (т.е. оказаться с ним на одном острове).Решение
Первый способ.Для того чтобы поймать шпиона, майору достаточно сначала приехать на остров, на котором находился шпион в первый день, а потом повторять маршрут шпиона. Поскольку майор не суеверен, то каждый месяц майор будет догонять шпиона на один переезд. Следовательно, через несколько месяцев майор догонит шпиона.
Второй способ.
Назовём расстоянием между островами минимальное число переездов, необходимое, чтобы попасть с одного острова на другой. Пусть майор каждый день выбирает кратчайший маршрут с его острова на остров шпиона и совершает первый переезд по этому маршруту. Тогда после его переезда расстояние от его острова до острова шпиона уменьшится на один. После переезда шпиона это расстояние увеличивается не более чем на один. Следовательно, в любой день это расстояние не увеличивается, а каждый месяц 13-го числа уменьшается на один. Следовательно, не более чем через 1 000 000 000 месяцев майор поймает шпиона.
Замечание. Время гарантированной поимки шпиона составляет 999 999 999/12 = 83 333 333 лет. Так что для поимки шпиона майору придётся стать долгожителем.
