Задача 5. Невидимая клетка

Что даёт один вопрос

Пронумеруем строки сверху вниз, а столбцы слева направо числами от $1$ до $5$; клетку в строке $r$ и столбце $c$ будем записывать как $(r,\,c)$. Четвёрка подряд идущих клеток — это либо клетки $1$–$4$ или $2$–$5$ какой-нибудь строки, либо строки $1$–$4$ или $2$–$5$ какого-нибудь столбца. Всего таких четвёрок $5\cdot2+5\cdot2=20$ (рисунок ниже).

Будем следить за подозреваемыми клетками — теми, которые ещё могут быть отмеченными. Сначала подозреваемых $25$. Ответ «да» оставляет под подозрением только клетки четвёрки — не больше $4$. Ответ «нет» снимает подозрение с клеток четвёрки — тоже не больше чем с $4$ клеток, а остальные подозреваемые остаются. Клетка определена, когда подозреваемая осталась одна.

Что значит «наверняка»? Способ задавать вопросы должен находить клетку, где бы её ни отметил Вася. Поэтому можно представить, что Вася хитрит: клетку он ещё не выбрал и отвечает так, как ему удобнее, лишь бы ответы не противоречили друг другу — то есть чтобы хотя бы одна клетка подходила под все его ответы. Если против такого Васи какой-то способ не справляется, он не справится и с честно отмеченной клеткой: у Васи найдётся клетка, при которой ответы были бы ровно такими же. В модели «Вопросы к Васе» Вася играет именно так.

Семи вопросов мало

Пусть кто-то утверждает, что находит клетку за $7$ вопросов. Пусть Вася на первые четыре вопроса — какими бы они ни были — отвечает «нет». Так ему можно: четыре четвёрки накрывают не больше $4\cdot4=16$ клеток, значит хотя бы $25-16=9$ клеток не входят ни в одну из них, и любая из этих клеток могла быть отмеченной (рисунок ниже).

Осталось $3$ вопроса, и на каждый есть два ответа. Значит, разных наборов ответов на три вопроса не больше $2\cdot2\cdot2=8$. А нетронутых клеток не меньше $9$. Для любой нетронутой клетки первые четыре ответа и так были бы «нет», поэтому после них начинается одно и то же дерево оставшихся вопросов. В нём следующие вопросы могут зависеть от предыдущих ответов, но листьев всё равно не больше восьми: на каждом из трёх уровней число ветвей увеличивается не более чем вдвое. Девять клеток, восемь наборов — по принципу Дирихле какие-то две нетронутые клетки дают одинаковые ответы на все семь вопросов. Если Вася отметил одну из них, после седьмого ответа мы не сможем сказать, какая из двух отмечена. Значит, семи вопросов не хватает, и ответ не меньше $8$.

Как это заметить: ответ «нет» — самый невыгодный для нас, он убирает всего четыре клетки. Поэтому полезно посчитать, сколько клеток останется, если Вася говорит «нет» подряд $1$, $2$, $3$, $4$ раза, и сравнить с числом наборов ответов $2^k$ на оставшиеся $k$ вопросов. При четырёх «нет» и получается $9>8$.

Стратегия за восемь вопросов: сначала четыре строки

Теперь покажем, что $8$ вопросов хватает всегда. Первые четыре вопроса зададим про строки $1$, $2$, $3$, $4$ — каждый раз про клетки $1$–$4$ (рисунок ниже). Как только услышим «да», скажем, про строку $i$, подозреваемых остаётся четыре: $(i,1)$, $(i,2)$, $(i,3)$, $(i,4)$. Их разбираем за три вопроса:

• строка $i$, клетки $2$–$5$: «нет» — отмечена $(i,1)$, и всё ясно; «да» — остались $(i,2)$, $(i,3)$, $(i,4)$;

• столбец $2$, строки $1$–$4$ (эта четвёрка содержит $(i,2)$, потому что $i\le4$): «да» — $(i,2)$; «нет» — остались $(i,3)$ и $(i,4)$;

• столбец $3$, строки $1$–$4$: «да» — $(i,3)$, «нет» — $(i,4)$.

В этом случае вопросов потрачено не больше $4+3=7$.

Зачем именно так: четыре вопроса про четыре разные строки накрывают $16$ клеток — ровно столько, сколько вообще могут накрыть четыре четвёрки. Если все четыре ответа «нет», нетронутыми остаются ровно $9$ клеток, а не больше: строка $5$ целиком и клетки $(1,5)$, $(2,5)$, $(3,5)$, $(4,5)$ столбца $5$ — уголок на рисунке. Эти $9$ клеток надо разобрать за оставшиеся четыре вопроса.

Уголок из девяти клеток за четыре вопроса

Подозреваемые: $(5,1)$, $(5,2)$, $(5,3)$, $(5,4)$, $(5,5)$ и $(1,5)$, $(2,5)$, $(3,5)$, $(4,5)$. Четырьмя вопросами можно различить не больше $2^4=16$ клеток, так что запас есть, но каждый вопрос должен делить подозреваемых с умом: после пятого вопроса в любой ветке должно остаться не больше $8$ клеток, после шестого — не больше $4$, после седьмого — не больше $2$.

Вопрос 5: строка $5$, клетки $2$–$5$.

«Да» — остались $(5,2)$, $(5,3)$, $(5,4)$, $(5,5)$. Вопрос 6: строка $5$, клетки $1$–$4$; «нет» — это $(5,5)$; «да» — остались $(5,2)$, $(5,3)$, $(5,4)$. Вопрос 7: столбец $2$, строки $2$–$5$ (содержит $(5,2)$): «да» — $(5,2)$; «нет» — осталось две. Вопрос 8: столбец $3$, строки $2$–$5$: «да» — $(5,3)$, «нет» — $(5,4)$.

«Нет» — остались $(5,1)$, $(1,5)$, $(2,5)$, $(3,5)$, $(4,5)$ — пять клеток, и их нужно разделить примерно пополам. Вопрос 6: столбец $5$, строки $2$–$5$ — из подозреваемых в нём $(2,5)$, $(3,5)$, $(4,5)$, а клетка $(5,5)$ уже снята с подозрения. «Да» — остались эти три: вопрос 7 — строка $2$, клетки $2$–$5$: «да» — $(2,5)$; «нет» — вопрос 8 — строка $3$, клетки $2$–$5$: «да» — $(3,5)$, «нет» — $(4,5)$. «Нет» — остались $(5,1)$ и $(1,5)$: вопрос 7 — столбец $1$, строки $2$–$5$: «да» — $(5,1)$, «нет» — $(1,5)$.

Во всех ветках не больше $8$ вопросов (дерево на рисунке ниже). Вместе с шагом 2 это даёт ответ: $8$.

Как искать такие вопросы: смотри, сколько подозреваемых попадёт в четвёрку, а сколько останется снаружи, и выбирай четвёрку так, чтобы большая из двух частей была как можно меньше — помня, что $k$ оставшихся вопросов различают не больше $2^k$ клеток.