Камень, который не может солгать дважды подряд

[worm2]

Эта задача предлагалась на прошедшей в Уфе республиканской олимпиаде школьников.
(точного условия не знаю, напеваю, как Рабинович "Битлов").

Рыцарь желает найти некое кольцо, которое находится в одном из $N$ зАмков.
Имеется камень, который знает, где именно находится кольцо.
Рыцарь может выбрать любое подмножество зАмков и спросить у камня, находится ли кольцо в одном из них.
Количество вопросов не ограничено.
На каждый вопрос камень отвечает "да" или "нет". При этом камень может сказать правду или неправду, однако он не может солгать два раза подряд.
По окончании допроса рыцарь посылает гонцов (каждый гонец едет в один зАмок).
Какого минимального количества $M=M(N)$ гонцов будет достаточно (после правильно организованного допроса), чтобы гарантированно найти кольцо?

[mihaild]

(Оффтоп)

Вроде двух.
Двух хватит:
1. Спросим про замок $A$.
1.1. Если сказали "нет", спросим еще раз про $A$.
1.1.1. Если опять сказали "нет", то кольцо точно не в $A$, уменьшили число замков на $1$.
1.1.2. Если сказали "да", перейти к 1.2.
1.2. Если сказали "да", спросим про пару $AB$.
1.2.1. Если опять сказали "да", то кольцо либо в $A$ либо в $B$.
1.2.2. Если сказали "нет", то кольцо точно не в $B$ (если оно там, то оба ответа ложные). Опять уменьшили число замков на $1$.
Итого за $\approx 3N$ вопросов остаемся с двумя замками. Вроде бы спрашивая не про отдельные замки, а про половины, можно получить тот же результат за $\approx 3 \log_2 N$, но нас это не просили.

Меньше двух нельзя (если $N > 1$).
Камень выбирает два замка $A$ и $B$, и поддерживает ответы, согласованные с обоими.
Все вопросы разбивает на блоки, содержащие вопросы про один из них, но не про другой, и остальные (про оба либо ни про один).
На вопросы, содержащие оба, отвечает "да" (правда в обоих вариантах). На вопросы, не содержащие ни одного, отвечает "нет" (тоже правда в обоих вариантах).
В блоке, в котором вопросы про ровно один из этих замков, на четные вопросы отвечает как будто кольцо в $A$, а на нечетные - как будто в $B$.

Gemini, кстати, не справилось, и вроде даже условий не поняло.

[worm2]

mihaild, всё верно.
Как вы быстро решили! Я часа три, наверное, думал, ошибался и передумывал.

[TOTAL]

Пристаю к первому замку, пока он не ответит ДА.

Затем спрашиваю у второго замка. Если тоже ДА, все замки, кроме первого и второго, пустые.
Если второй отвечает НЕТ, то опять пристаю к первому, пока он не ответит ДА.

Затем спрашиваю у третьего замка. Если тоже ДА, все замки, кроме первого и третьего, пустые.
Если третий отвечает НЕТ, то опять пристаю к первому, пока он не ответит ДА.

Таким способом (допрашивая другие замки после ДА первого замка) либо сужаем число перспективных замков до двух, либо (если все другие отвечали НЕТ) находим кольцо в первом замке.

[Null]

TOTAL в сообщении #1717318 писал(а):

Пристаю к первому замку, пока он не ответит ДА.

Никогда же возможно?

[worm2]

Null, камню "невыгодно" одинаково отвечать на один и тот же вопрос два раза подряд, поскольку он тем самым даёт информацию, что оба ответа истинные.

[TOTAL]

Пусть всего три замка (три группы замков).
За $10$ вопросов $1,2,1,3,1,1,3,1,2,1$ можно отбраковать одну или две группы. А за меньшее число?
Список вопросов фиксирован, следующий вопрос не зависит от ответов на предыдущие.

$2,1,3,1,1,3,1,2$