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

Турбо атты ұлу 2024 жолы және 2023 бағаны бар тақтада келесі ойын ойнайды. Тақтаның 2022 ұяшығында құбыжықтар тығылып отыр. Турбо бастапқыда құбыжықтардың қай ұяшықта отырғанын білмейді, бірақ ол бірінші және соңғы жолдан басқа әр жолда дәл бір құбыжық бар екенін; және әр бағанда ең көп дегенде бір құбыжық бар екенін біледі.
   Турбо бірінші жолдан соңғы жолға өтетіндей бірнеше әрекет жасайды. Әрбір әрекетте ол бірінші қатардағы кез келген ұяшықты бастапқы ұяшық ретінде таңдап алып, содан кейін ортақ қабырғасы бар көрші ұяшыққа өту серияларын жасайды. (Оған бұрын барған ұяшықтарға оралуға рұқсат.) Егер ол құбыжығы бар ұяшыққа түссе, онда оның осы кезектегі әрекеті аяқталады да, ол қайтадан бірінші жолға қайтарылады. Құбыжықтар қозғалмайды және Турбо ол барған әрбір ұяшықта құбыжықтың бар-жоғын есіне сақтап отырады. Егер Турбо осылай соңғы қатардағы кез келген ұяшыққа жетсе, оның әрекеті аяқталған болып есептеледі және ойын аяқталады.
   Құбыжықтардың орналасуына қарамастан Турбо $n$ немесе одан аз әрекет санында соңғы ұяшыққа жете алатындай стратегия ойлап таба алатындай ең кіші $n$ санын табыңыз.

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

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

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

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

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

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

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

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

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

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

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