ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 78678
Тема:    [ Теория игр (прочее) ]
Сложность: 3+
Классы: 9,10
В корзину
Прислать комментарий

Условие

Страна Фарра расположена на 1 000 000 000 островов. Между некоторыми островами каждый день курсируют пароходы. Маршруты пароходов устроены так, что с каждого острова можно попасть на любой другой (возможно, за несколько дней). Шпион и майор Пронин могут совершать не более одного рейса в день на пароходе и не имеют никакой другой возможности попасть с острова на остров. Шпион не ездит на пароходе 13 числа каждого месяца, майор Пронин не суеверен и всегда знает, где находится шпион. Доказать, что майор сможет поймать шпиона (т.е. оказаться с ним на одном острове).
Также доступны документы в формате TeX

Решение

Первый способ.

Для того чтобы поймать шпиона, майору достаточно сначала приехать на остров, на котором находился шпион в первый день, а потом повторять маршрут шпиона. Поскольку майор не суеверен, то каждый месяц майор будет догонять шпиона на один переезд. Следовательно, через несколько месяцев майор догонит шпиона.

Второй способ.

Назовём расстоянием между островами минимальное число переездов, необходимое, чтобы попасть с одного острова на другой. Пусть майор каждый день выбирает кратчайший маршрут с его острова на остров шпиона и совершает первый переезд по этому маршруту. Тогда после его переезда расстояние от его острова до острова шпиона уменьшится на один. После переезда шпиона это расстояние увеличивается не более чем на один. Следовательно, в любой день это расстояние не увеличивается, а каждый месяц 13-го числа уменьшается на один. Следовательно, не более чем через  1 000 000 000 месяцев майор поймает шпиона.

Замечание. Время гарантированной поимки шпиона составляет  999 999 999/12 = 83 333 333 лет. Так что для поимки шпиона майору придётся стать долгожителем.
Также доступны документы в формате TeX

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 31
Год 1968
вариант
1
Класс 8
Тур 2
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .