Международная олимпиада 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 он уже может ступать безопастно в ряд и столбец где назодился монстр то что он знает что этот ряд безопасен много ему не даст, ведь его цель двигаться вниз, а в свою очередь что бы безопастно двигаться вниз по безопастному столбцу ему нужно как минимум встать в ряд который на клетку ниже безопастного но так как турбо не может двигаться по диагонали то он не сможет сразу встать в клетку безопастного столбца в ряду который на клетку ниже безопастного ряда.