Тимлид и джун играют в игру. Тимлид выбирает целое...

Ниже приведено одно из возможных рассуждений, показывающее, что после 8 раундов (то есть 8 пар вопросов) в худшем случае может остаться ровно 1 подходящее значение p (то есть число угадывается однозначно).

────────────────────────────────────────────────────

1. Какую информацию даёт каждая пара вопросов ────────────────────────────────────────────────────

Пусть в одном раунде джун задаёт два вопроса Q_1 и Q_2, каждый из которых имеет правильный ответ «да» или «нет» в зависимости от выбранного тимлидом числа p. Обозначим правильные ответы (то есть те, которые соответствуют действительному числу p) через T_1 и T_2. Поскольку тимлид обязан:

• на один из вопросов ответить правду,
• а на другой солгать,

то возможные итоговые пары ответов (A_1, A_2), которые джун услышит, — это либо

• (T_1, ¬T_2),
• (¬T_1, T_2),

где «¬» означает логическое НЕ (замена «да» ↔ «нет»).

Заметим важную особенность:

• Если T_1 = T_2, то после «переворота» ровно одного ответа получится «один да и один нет» (пара разных ответов).
• Если T_1 ≠ T_2, то «переворот» одного ответа даёт пару одинаковых ответов (оба «да» или оба «нет»).

Иными словами, увидев пару (A_1, A_2), джун не может достоверно узнать, какой из них — правда, а какой — ложь, однако он точно знает:

• либо T_1 = T_2, если (A_1, A_2) — ответы разного типа («да/нет» или «нет/да»),
• либо T_1 ≠ T_2, если (A_1, A_2) — ответы одинакового типа («да/да» или «нет/нет»).

Таким образом, каждая пара вопросов фактически даёт джуну ровно 1 бит информации: «совпадают ли истинные ответы на Q_1 и Q_2 (T_1 = T_2) или нет (T_1 ≠ T_2)».

──────────────────────────────────────────────────── 2. Объём информации и возможность закодировать число ────────────────────────────────────────────────────

Всего чисел p от 1 до 100, значит нам нужно уметь различать 100 вариантов. Для распознавания 100 разных значений достаточно log_2(100) ≈ 6,64 бит информации. Поскольку в задаче есть 8 раундов, и каждый даёт ровно 1 бит (совпадение ответов или несовпадение), итого мы можем получить до 8 бит, что достаточно, чтобы однозначно «закодировать» любое p из 100.

──────────────────────────────────────────────────── 3. Как строить вопросы (схематически) ────────────────────────────────────────────────────

Идея в том, чтобы в каждом раунде разбивать текущее множество кандидатов для p примерно пополам в зависимости от того, совпадут ли ответы на Q_1 и Q_2 или нет. Формально это можно устроить так:

1. Нумеруем числа от 1 до 100.
2. В каждом раунде выбираем два вопроса Q_1 и Q_2, которые устроены так, что для «левой» половины возможных p ответы должны совпадать, а для «правой» половины — не совпадать, и наоборот (или любой иной способ «равномерно» разбить оставшееся множество).
3. После того как тимлид даёт пару (A_1, A_2), джун понимает, совпали ли истинные ответы T_1 и T_2, и тем самым отбрасывает примерно половину оставшихся кандидатов.

Благодаря последовательному уточнению за 8 шагов множество возможных значений p сузится до одного единственного.

──────────────────────────────────────────────────── 4. Итог ────────────────────────────────────────────────────

В худшем случае (при самых невыгодных для джуна ответах со стороны тимлида, но при оптимальных вопросах джуна) после 8 пар вопросов остаётся ровно 1 возможное значение p. Иными словами, минимально возможное n (число «неотсеянных» кандидатов) равно 1.