Международная олимпиада 2024, Бат, Великобритания, 2024 год

Улитка Турбо играет на доске, имеющей 2024 ряда и 2023 столбца, в следующую игру. В 2022 клетках доски прячутся монстры. Изначально Турбо не знает, где находится какой-либо из монстров, но она знает, что в каждом ряду, кроме первого и последнего, есть ровно один монстр и что в каждом столбце находится не более одного монстра.
   Турбо делает серию попыток, чтобы пройти из первого ряда в последний. При каждой попытке она может выбрать в качестве начальной любую клетку в первом ряду, а затем совершает серию перемещений из клетки в соседнюю клетку, имеющую общую сторону. (Ей разрешается возвращаться в ранее посещенные клетки.) Если она посещает клетку с монстром, то её попытка завершается, и она переносится обратно в первый ряд, чтобы начать новую попытку. Монстры не двигаются, а Турбо запоминает, есть ли в каждой посещенной ею клетке монстр. Если она достигнет любой клетки в последнем ряду, её попытка завершается, и игра оканчивается.
   Определите минимальное значение $n$ такое, что у Турбо есть стратегия, которая, независимо от местонахождений монстров, гарантирует достижение последней строки за $n$ попыток или раньше.

Комментарий/решение

Ответ: 3

Оценка: Заметим, что когда турбо приходит в 2 ряд, тогда он может напороться на монстра, откуда -1 попытка, в следующем, так как он не в предыдущей клетке, он спокойно может напороться на другого монстра отсюда еще -1 попытка значит попыток хотябы 3

Давайте придумаем стратегию для 3 попыток:

Потратим одну попытку на нахождения монстра в 2 ряду и у нас есть два случая:

1) Этот монстр не в конце, тогда мы не более чем за 2 попытки подбираемся под него и дальше легко

2) Этот монстр в конце, тогда будем идти в противоположоный конец третьего ряда и рассмотрим две клетки до монстра. Если там есть монстр то можно прокрасться под монстром второго ряда создавая "лестницу", если монстров нет, то лестница дойдет до конца. Например, если первый монстр в (2;1) тогда:

(2,2)->(2,3)->(3,3)->(3,4)->...->(2024;2023).