Минимизация возможных значений

Question

Тимлид и джун играют в игру. Тимлид выбирает целое число 𝑝 от 1 до 100, а джун пытается его угадать. В каждом раунде джун задаёт тимлиду два вопроса, на которые можно ответить «да» или «нет». Тимлид обязан на один из вопросов ответить правду, а на другой — солгать. После 8 раундов джун делает вывод, что возможных значений для 𝑝 осталось 𝑛. Каково минимальное значение 𝑛, если тимлид выбирает ответы, максимально усложняющие задачу для джуна?

Answer 1

Анализ задачи

У нас есть число $p$ от 1 до 100.
За один раунд джун задаёт два вопроса с ответами «да/нет», причём тимлид обязан на один из них ответить правдиво, а на другой — солгать (но джун не знает, какой из ответов был честным, а какой — нет).
После 8 раундов (то есть после 8 пар вопросов) остаётся некоторое множество возможных значений $p$ , и нас просят найти минимальный размер этого множества (в худшем случае для джуна, при максимально «запутывающих» ответах тимлида).

На первый взгляд ситуация сложная, ведь каждый раунд даёт «смешанные» ответы, один из которых истинный, а другой ложный. Однако есть удобный способ смотреть на каждый раунд чисто комбинаторно, сводя его к задаче «разбиения множества» с особым правилом.

Как интерпретировать один раунд

Пусть в каком-то раунде джун задаёт два вопроса $Q_1$ и $Q_2$ . Для конкретного числа $p$ :

Истинные ответы на эти вопросы образуют пару $\bigl(T_1, T_2\bigr)$ , где $T_i \in \{\text{«да»}, \text{«нет»}\}$ .
Однако тимлид даёт пару ответов $\bigl(A_1, A_2\bigr)$ , отличающуюся от $\bigl(T_1, T_2\bigr)$ ровно в одной координате (т.,е. солжёт на одном вопросе и скажет правду на другом).

Таким образом, если бы мы заранее каждому $p$ приписали пару «настоящих» ответов $\bigl(T_1, T_2\bigr)$ , то наблюдаемые ответы $\bigl(A_1, A_2\bigr)$ будут находиться на расстоянии Хэмминга 1 от $\bigl(T_1, T_2\bigr)$ .

С точки зрения джуна, увидев пару $\bigl(A_1, A_2\bigr)$ , он понимает лишь, что «истинная» пара $\bigl(T_1, T_2\bigr)$ (то есть правильные ответы для числа $p$ ) должна отличаться от $\bigl(A_1, A_2\bigr)$ ровно в одном бите. Но какой именно бит «перевран», он не знает.

Как «кодировать» множество чисел

Пусть к началу некоторого раунда множество возможных значений $p$ есть $S$ . Джун может выбрать два вопроса так, чтобы заранее (до ответа тимлида) разбить $S$ на 4 части по принципу:

Для каждого $p \in S$ вычисляем пару
$Q(p) \;=\; \bigl(q_1(p),\,q_2(p)\bigr) \;\in\; \{0,1\}^2,$
где $q_1(p)\in\{0,1\}$ соответствует ответу «да/нет» на первый вопрос (если бы отвечали правдиво),
а $q_2(p)\in\{0,1\}$ — на второй.

Обозначим 4 подмножества:
$A = Q^{-1}((0,0)),\quad B = Q^{-1}((0,1)),\quad C = Q^{-1}((1,0)),\quad D = Q^{-1}((1,1)).$
Тогда очевидно,
$A \cup B \cup C \cup D \;=\; S,\quad A,\,B,\,C,\,D \;\text{попарно непересекаются}.$

После ответа тимлида джун видит пару $(A_1,A_2)$ , которая ровно на 1 бит отличается от истинной $\bigl(q_1(p),\,q_2(p)\bigr)$ . Но джун знает лишь «наблюдаемую» пару, из которой следует:

$p$ должен лежать в том подмножестве $S_x$ (новое множество), для которого $\bigl(q_1(\cdot),\,q_2(\cdot)\bigr)$ может дать пару, отличающуюся от $(A_1,A_2)$ на 1 бит.

В двоичной записи $\{0,1\}^2$ «соседями» (расстояние Хэмминга 1) являются:

$(0,0)$ и $(0,1)$ , $(0,0)$ и $(1,0)$ ,
$(1,1)$ и $(1,0)$ , $(1,1)$ и $(0,1)$ .

То есть в виде квадрата:

text
   (0,0) --- (1,0)
     |         |
   (0,1) --- (1,1)

Оказывается, при любом ответе:

Если пришёлся ответ «(0,0)», то возможными $p$ будут все из $B \cup C$ .
Если ответ «(0,1)», то возможными будут $A \cup D$ .
Если ответ «(1,0)», то тоже $A \cup D$ .
Если ответ «(1,1)», то $B \cup C$ .

Тимлид в худшем для нас случае «оказывается» (истинной парой) в том углу, после ответа из которого останется максимальное из возможных объединений. То есть после такого раунда размер нового множества равен:

\max\bigl(\lvert A \cup D\rvert,\;\lvert B \cup C\rvert\bigr).

Но $A,B,C,D$ — непересекающиеся множества, так что

|A \cup D| = |A| + |D|,\quad |B \cup C| = |B| + |C|.

Следовательно, оптимальным для джуна будет (как можно) уравнять суммы $|A|+|D|$ и $|B|+|C|$ , стараясь, чтобы они были поменьше.

«Двоичное» деление пополам

Если в начале раунда у нас множество $S$ из $n$ элементов, то мы можем (задав подходящие два вопроса) разбить его примерно на 4 равные части $A,B,C,D$ , чтобы:

$|A|+|D|\approx \frac{n}{2}$ ,
$|B|+|C|\approx \frac{n}{2}$ .

В идеале (если $n$ делится на 4) можно добиться $|A|=|B|=|C|=|D|=\frac{n}{4}$ . Тогда

\max(|A|+|D|,\;|B|+|C|) \;=\; \frac{n}{4} + \frac{n}{4} \;=\; \frac{n}{2}.

Если $n$ не делится на 4, делаем «почти равномерное» разбиение, и в любом случае худший случай не превысит $\lceil \tfrac{n}{2} \rceil$ .

Таким образом, каждый раунд гарантированно умеет «схлопывать» множество возможных $p$ примерно вдвое (максимум в $\lceil n/2\rceil$ ).

Сколько раундов нужно, чтобы сузить 100 чисел до 1

Начальное множество размеров 100. Покажем, как оно уменьшается после каждого «пополам»‑раунда:

После 1-го раунда: $\le 50$ .
После 2-го раунда: $\le 25$ .
После 3-го: $\le 13$ .
После 4-го: $\le 7$ .
После 5-го: $\le 4$ .
После 6-го: $\le 2$ .
После 7-го: $\le 1$ .

Уже после 7 раундов можно дойти до множества размера $1$ . А значит, и после 8-го (тем более) «хвост» не вырастет. То есть к концу 8 раундов джун может точно знать число $p$ . Иначе говоря, в самом худшем случае (при максимально запутывающих ответах тимлида), размер множества «ещё возможных» чисел может быть стеснён вплоть до:

n = 1.

Ответ

\boxed{1.}

То есть при наилучшей стратегии вопросов со стороны джуна и «запутывающей» стратегии ответов со стороны тимлида после 8 раундов остаётся не более одного возможного варианта для $p$ . Иначе говоря, можно однозначно вычислить число за 8 «двойных» вопросов.