ВСОШ 2026, региональный этап, 10 класс, задача 5
( баллов) В Средиземье графств, в одном из которых находится волшебное Кольцо. Раз в день Маг может выбрать любое подмножество графств и получить от волшебного Камня ответ, есть ли Кольцо в одном из этих графств. Камень может ошибиться, но никогда не ошибается два дня подряд. Маг может совершать данное действие некоторое количество дней, после чего он должен отправить гонцов в некоторые графств, в одном из которых наверняка находится Кольцо. При каком наименьшем Маг может это сделать?
Ответ
Ответ. .
Решение.
Оценка. Покажем, что при Маг не сможет гарантированно найти Кольцо.
Назовём одно из графств без Кольца лжеграфством. Пусть Камень отвечает на нечётных вопросах так, будто Кольцо в истинном графстве, а на чётных — будто оно во лжеграфстве. Тогда какие бы графства Маг ни загадывал, будут возможны две ситуации: Кольцо в истинном графстве или во лжеграфстве. Действительно, в первом случае Камень отвечает верно по крайней мере на нечётных вопросах, во втором — на чётных. Поэтому Маг не сможет отличить эти ситуации ни за какое количество вопросов.
Пример. Покажем, как Маг может гарантированно разыскать Кольцо при . Выберем какие-то два графства и : первое и второе. Зададим подряд вопросы про , , , .
. Если Камень на первые два вопроса ответил соответственно «да» и «нет», то т.к. среди этих ответов был хотя бы один верный, в графстве гарантированно нет Кольца.
. Если он ответил «нет» и «да», в нет Кольца.
. Если Камень на первые два вопроса ответил «да» и «да», то т.к. среди этих ответов был хотя бы один верный, Маг сразу отправит гонцов в и .
. Если Камень на первые два вопроса ответил «нет» и «нет», смотрим на третий вопрос. Если ответ «нет», то поскольку среди второго и третьего ответов был хотя бы один верный, в графстве нет Кольца.
Если же ответ на третий вопрос — «да», смотрим на четвертый вопрос. Если ответ «да», получаем с двумя последними вопросами такую же ситуацию, как в случае . Если ответ «нет», получаем ситуацию из случая .
В результате таких действий с двумя графствами и Маг либо немедленно найдет Кольцо, либо сможет понять про одно из них, что в нём кольца нет. Тем самым, задача сведена к той же задаче с меньшим числом графств. Повторяя такие действия, Маг добьётся требуемого.