Доказательство: детектив задаёт $q < n$ вопросов. Каждый вопрос вовлекает одного «отвечающего» и одного «обсуждаемого». За $q$ вопросов затронуто не более $2q < 2n$ жителей, но возможны повторения. Ключевое: граф вопросов (ориентированный граф, где дуга i$\to$j означает «$i$ был спрошен о $j$») содержит не более $q$ дуг. В графе на $n$ вершинах с менее чем $n$ дугами существует хотя бы одна вершина $v$ с нулевой входящей степенью (не было задано ни одного вопроса о $v$ никому) или ребро, не вошедшее в остовное дерево. Если существует житель $v$, о котором не спрашивали никого, противник может назначить $v$ любой тип — детектив не имеет информации о $v$ и угадывает с вероятностью не 1. В детерминированном варианте: противник заранее знает алгоритм детектива, поэтому заранее выбирает расстановку, при которой ответ детектива о $v$ неверен. Формально: детектив выдаёт детерминированный ответ для $v$, не зависящий от её типа (нет вопросов о v). Противник выбирает тип $v$ противоположным предсказанию детектива. Детектив ошибается по $v$. Выигрышная стратегия противника при $q < n$ доказана.

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