Найти тему
mathreshka

Решение. Catcher in the Rye (#46)

Условие

Ответ: да

Решение:

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

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

Замечание 1. В случае трёх нор алгоритм поимки таков: 2 2.

Замечание 2. Легко видеть, что данный подход легко обобщается на случай произвольного количества n нор. Последовательность поимки: 2 3 … (n-2) (n-1) (n-1) (n-2) … 3 2.