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

[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$

[geos]

Если возможно представить N замков как линейную последовательность, то хватит 1 гонца.
Все замки это последовательность от A до N.
Делим её пополам на 2 подмножества и задаём (максимум 3 раза) вопрос: "Находится ли кольцо в подмножестве замков от A до N/2".
Если да, то работаем с этим подмножеством дальше, если нет, то работаем с подмножеством от N/2+1 до N.
Когда следующее подмножество определено, снова делим его пополам. И так далее, пока оно не сократится до 2 замков.
Когда их останется 2, то можно однозначно выяснить в каком из них находится кольцо и использовать одного гонца.

Если же по условию рыцарь может спрашивать только про подмножество замков и не может задавать вопрос про конкретный замок, т.е. замков должно быть как минимум 2, тогда ответом будет - 2 гонца.

[mihaild]

geos в сообщении #1718406 писал(а):

Делим её пополам на 2 подмножества и задаём (максимум 3 раза) вопрос: "Находится ли кольцо в подмножестве замков от A до N/2".

Получили ответы "да, нет, да". Что дальше?

geos в сообщении #1718406 писал(а):

Когда их останется 2, то можно однозначно выяснить в каком из них находится кольцо

Каким образом?

[Predictor]

Делим множество замков $N$ на 2 подмножества: одно из них равно максимально возможному $2^n<N$, а другое - $N-2^n$, трижды спрашиваем в каком из подмножеств кольцо и однозначно это определяем. Если оно в первом подмножестве, то задаем $n$ вопросов и устанавливаем где камень за $n+3$ вопросов, а если во втором, то не более чем за $n+3$, где $n=\lfloor(log_2(N))\rfloor$. Итого, минимальное количество гонцов равно 1. А количество заданных вопросов равно $\lfloor(log_2(N))\rfloor+3$.
P.S. Предполагаю, что вопрос задачи был о минимальном количестве вопросов, чтобы определить где точно находится камень, т.к. при неограниченном количестве вопросов всегда можно найти единственно правильный замок и послать туда одного гонца.

[Mikhail_K]

Predictor в сообщении #1718421 писал(а):

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

Нет, нельзя, и выше это обосновано.

Predictor в сообщении #1718421 писал(а):

трижды спрашиваем в каком из подмножеств кольцо и однозначно это определяем

mihaild в сообщении #1718420 писал(а):

Получили ответы "да, нет, да". Что дальше?

[Predictor]

Mikhail_K в сообщении #1718425 писал(а):

Predictor в сообщении #1718421 писал(а):

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

Нет, нельзя, и выше это обосновано

можно например спрашивать про каждый замок 5 раз. Если хотя бы 3 ответа среди пяти одинаковые, то они истинны. Так установим однозначно в каком замке кольцо. Что не так в этом подходе?

Mikhail_K в [url=http://dxdy.ru/post1718425.html#p1718425]
[quote="Predictor в сообщении #1718421 писал(а):

трижды спрашиваем в каком из подмножеств кольцо и однозначно это определяем

mihaild в сообщении #1718420 писал(а):

Получили ответы "да, нет, да". Что дальше?

[/quote]
Спрашиваем еще 2 раза. Хотел сразу написать 5, но почему-то написал 3.

[Mikhail_K]

Predictor в сообщении #1718429 писал(а):

можем например спрашивать про каждый замок 5 раз

Получили ответы "да", "нет", "да", "нет", "да". Что дальше?

Predictor в сообщении #1718429 писал(а):

Если хотя бы 3 ответа среди пяти одинаковые, то они истинны.

Нет, если среди этих трёх ответов нет идущих подряд, то нет гарантий их истинности.

[geos]

mihaild в сообщении #1718420 писал(а):

geos в сообщении #1718406 писал(а):

Делим её пополам на 2 подмножества и задаём (максимум 3 раза) вопрос: "Находится ли кольцо в подмножестве замков от A до N/2".

Получили ответы "да, нет, да". Что дальше?

geos в сообщении #1718406 писал(а):

Когда их останется 2, то можно однозначно выяснить в каком из них находится кольцо

Каким образом?

Вы правы, камень может чередовать ответы "да", "нет", "да". Давайте посмотрим на варианты. Итак, мы разделили все подмножество на 2 группы и получили группу А и группу B.
Мы 2 раза задаем вопрос "Кольцо в группе А?". Если камень даёт 2 одинаковых ответа, тогда всё очевидно. Если он начинает чередовать Да/Нет, тогда 3-й вопрос мы задаём про группу B. И тут возникают 2 варианта.

Вариант 1 (3-й ответ камня НЕ совпадает со 2-м):

          Группа А   Группа B
шаг 1       Да
шаг 2       Нет
шаг 3                   Да

Вывод: однозначно в B

или обратная ситуация

          Группа А   Группа B
шаг 1       Нет
шаг 2       Да
шаг 3                   Нет

Вывод: однозначно в A

Вариант 2 (3-й ответ камня совпадает со 2-м):

          Группа А   Группа B
шаг 1       Да
шаг 2       Нет
шаг 3                   Нет

Вывод: невозможно определить

или обратная ситуация

          Группа А   Группа B
шаг 1       Нет
шаг 2       Да
шаг 3                   Да

Вывод: невозможно определить

Если мы получаем вариант 2, который не даёт однозначного определения нужной группы, тогда можно пойти другим путём и переформулировать вопрос так, чтобы любой ответ на него был заведомо ложный.
Например так: "Кольцо одновременно и в группе А и в группе B?".
Любой ответ на этот вопрос будет ложным и следующий вопрос определит нужную группу.
Конечно, это некая уловка и она возможна только в том случае если условие задачи допускает такие вопросы.

Второй Ваш вопрос не совсем понял, но если Вы про сам процесс деления групп, то выглядит он примерно так:

шаг 1: (Замок1 Замок2 Замок3 Замок4 Замок5)      (Замок6 Замок7 Замок8 Замок9 Замок10)
|               /                    \    
|              /                      \
шаг 2: (Замок1 Замок2)      (Замок3 Замок4 Замок5)
|                               /            \
|                              /              \  
шаг 3:                    (Замок3)       (Замок4 Замок5)
|                                          /           \
|                                         /             \
шаг 4:                                (Замок4)       (Замок5)

[worm2]

geos, просто представьте себе такую стратегию камня: к замку A, в котором находится кольцо, он добавляет другой замок B, и чередует ответы: на чётные вопросы отвечает правдиво, а на нечётные — как будто камень в замке B (иногда этот ответ тоже будет правдой, например, если заданное множество включает в себя оба замка). Или наоборот: на нечётные отвечает правдиво. И рыцарь, даже зная заранее эту стратегию и множество {A, B}, не сможет определить, по чётным ли номерам камень отвечает правдиво или же по нечётным.