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

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

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

турбо может использовать следующую стратегию

в первой попытке она начинает с первого столбца и проверяет все клетки в этом столбце (с 1 по 2024)

во второй попытке она начинает со второго столбца и также проверяет все клетки в этом столбце

в третьей попытке она начинает с третьего столбца и проверяет все клетки в этом столбце

поскольку в каждом ряду кроме первого и последнего есть ровно один монстр и в каждом столбце может быть не более одного монстра то

если в первом столбце есть монстр турбо его обнаружит в первой попытке

если монстр находится во втором или третьем столбе она обнаружит его во второй или третьей попытке соответственно

таким образом за 3 попытки она сможет гарантированно проверить все возможные случаи

таким образом выходит что n=3

Ответ 3 попытки

Ответ: $n = 3$

Оценка: Очевидно что $n=1,2$ не подходят.

Пример: Пронумеруем строки сверху вниз и столбцы слева направо, тогда клетка $(x,y)$ - это клетка на пересечений строки $x$ и столбца $y$. За первый ход узнаем где находится монстр во втором ряду. Пусть в клетке $(m,n)$ , если это не $(2,1) $ и не $(2,2023)$ то в одном из клеток $(m+1,n-1)$ или $(m+1,n+1)$ нету монстра. Тогда просто идем в ту клетку и в клетку $(m+1,n)$ и просто спускаемся вниз. Пусть теперь монстр во втором ряду находится в клетке $(2,1)$ . Тогда рассмотрим последовательность ходов $(1,1),(1,2),(2,2)(2,3),(3,3)...$ то есть что-то вроде лестницы.

Пусть на клетке $(a,b)$ мы встретили монстра , на третьем ходу обратно придем но уже пойдем в клетку $(a,b-1)$ и далее просто из $b-1$ - го столбца по строке $a$ идем в клетку $(a,1)$ и просто спускаемся вниз и при этом очевидно что мы не встретим монстров. Так за не более чем $3$ хода мы спустились на последнюю строку.

Интересно почему n=1,2 не подходят

Для n=1 очевидно что ответ нет, тк турбо попросту не имеет даже понятие где монстры.

Вот для n=2 он уже может ступать безопастно в ряд и столбец где назодился монстр то что он знает что этот ряд безопасен много ему не даст, ведь его цель двигаться вниз, а в свою очередь что бы безопастно двигаться вниз по безопастному столбцу ему нужно как минимум встать в ряд который на клетку ниже безопастного но так как турбо не может двигаться по диагонали то он не сможет сразу встать в клетку безопастного столбца в ряду который на клетку ниже безопастного ряда.