Павел
По кругу стоят лжецы, рыцари и Павел. Мы можем задавать вопросы (они обязаны подразумевать ответ да/нет), всегда начиная с одного человека и спрашивая их по часовой стрелке. Каждый вопрос мы обязаны задать всем в кругу. Павел на первом кругу отвечает так же, как его первый островитянин слева, на втором – как второй, и так далее. За какое минимальное число вопросов можно гарантированно найти Павла?
Решение
За один вопрос нельзя, так как мы узнаём статус множества. А для Павла нам нужен отдельный статус двух агентов. Поэтому мы не можем одновременно подтвердить тип и узнать про Павла. Первый вопрос: "Если вашего соседа слева спросят, Павел ли он, что он ответит?". "нет" ответят только комбинации РР, ЛЛ, ПР и ПЛ, Павел "да" говорить не будет. Если мы рассмотрим все ответы нет, то начиная с первого человека, комбинации для нет, нет включают \{РРР, ЛЛЛ, ПЛЛ, ПРР\}, а для да, да — \{РРЛ, ЛЛР, ПЛР, ПРЛ\}. Теперь спросим: "Вы Павел?". Из выше включённых комбинаций, тройки с Павлом ответят: -++, +—, ++- и +-+, уникально для всех троек, у которых первый человек ответил "нет". Значит ищем тройку, начинающуюся с "нет" на первый вопрос и подходящим набором ответов на второй.
Ответ: 2
Ответ: 2