На острове живут рыцари, лжецы и нормальные. Вам нужно выбрать одного рыцаря из трёх жителей А, Б, В. Какое наименьшее количество вопросов типа «да/нет» достаточно, чтобы гарантированно выбрать рыцаря? Предложите алгоритм.
Правильный ответ
Достаточно трёх вопросов. Спросите А: «Является ли Б рыцарем?» Если «да» — спросите Б: «Является ли В рыцарем?» и затем В: «Ты рыцарь?» Анализируя три ответа, можно вычислить, кто из троих рыцарь. Двух вопросов в худшем случае недостаточно: нормальный может дать произвольный ответ, делая задачу неразрешимой.
💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!