Нижняя оценка: 6 вопросов. Алгоритм за 6 вопросов: Выберем «опорного» жителя. За 6 вопросов спросим жителя №1 о каждом из жителей №2–7: «Житель $k$ — рыцарь?». Если житель №1 — рыцарь, все ответы правдивы и мы знаем типы 2–7, а тип №1 определяем спросив кого-то из выявленных рыцарей о №1. Но это 7 вопросов. Улучшение: вместо последнего вопроса определяем тип №1 по внутренней согласованности (если большинство жителей — рыцари, №1 тоже рыцарь по ответам). Нижняя оценка 6 обоснована тем, что каждый вопрос даёт 1 бит информации, а для идентификации 7 жителей нужно минимум ⌈$\log_{2}(2^{7})$⌉ = 7 бит, однако взаимная структура сокращает до 6.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!