Доказательство нижней оценки $n-1$ вопросов: рассмотрим адверсарный аргумент. Противник (адверсарий) отвечает на вопросы детектива, сохраняя возможность двух различных расстановок типов, совместимых со всеми ответами. Предположим, детектив задал менее $n-1$ вопросов. Тогда существует пара жителей $(i, j)$, о которых ни один не был спрошен ни у кого, и которые не спрашивали других. Адверсарий может поменять типы $i$ и $j$ местами: если $i$ был рыцарем, $j$ лжецом — заменить. При этом ни один из полученных ответов не противоречит новому распределению (так как $i$ и $j$ не участвовали в вопросах). Оба распределения совместимы с историей вопросов — детектив не может отличить их. Следовательно, алгоритм, задавший менее $n-1$ вопросов, не может гарантированно определить типы всех жителей. Нижняя оценка $n-1$ доказана.

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