Доказательство: пусть алгоритм задаёт ровно $k$ вопросов ($k$ фиксировано) и задействует жителей из конечного множества $S = \{v_{1}, \ldots, v_{m}\}$. Рассмотрим расстановку, при которой все жители из $S$ — лжецы, а все остальные — рыцари. Ответы лжецов на все вопросы вида «$v_i$ — рыцарь?» будут ложными. Теперь рассмотрим вторую расстановку: все жители — лжецы. В этой расстановке ответы тех же жителей из $S$ на те же вопросы будут идентичны (лжецы отвечают симметрично). Алгоритм получает одинаковую историю ответов в обоих случаях, но в первой есть рыцари, во второй — нет. Если алгоритм называет кого-то рыцарем, в расстановке «все лжецы» он ошибается. Если не называет — в первой расстановке ошибается. Следовательно, для любого детерминированного алгоритма с конечным $k$ существует расстановка, при которой он ошибается.

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