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

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

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

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

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

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

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

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

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

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

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

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

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