Условие

Двое играют в следующий вариант «морского боя». Один игрок располагает на доске $n×n$ некоторое количество непересекающихся «кораблей» $n×1$ (быть может, ни одного). Второй игрок наносит одновременно ряд ударов по полям доски и про каждое поле получает от противника ответ — попал или промахнулся. По какому минимальному количеству полей следует нанести удары, чтобы по ответам противника можно было однозначно определить расположение всех его кораблей? Рассмотрите три случая: а) $n=4$, б) $n=10$, в) $n$ — любое натуральное число.

Решение

Как показывают письма читателей, формулировка задачи допускает два одинаково осмысленных толкования — в зависимости от того, какие корабли считать «непересекающимися» $(1)$ те, которые не имеют общих клеток; $(2)$ те, которые вообще не имеют общих точек, даже граничных — как это принято в обычной игре «морской бой», в которую все мы играли в детстве. Обе задачи получились довольно интересными, хотя $(1)$, пожалуй, попроще. С нее мы и начнем.

$(1)$ Пусть корабли заполняют произвольное множество $K$ из нескольких горизонталей или вертикалей доски $n×n$; мы должны указать множество $A$ из возможно меньшего числа клеток такое, что пересечение $A\cap K$ однозначно определяет множество $K$. (Заметим, что если кораблей $n$, то они занимают все клетки доски, и мы, разумеется, никак не сможем узнать, горизонтальные корабли или вертикальные.)

Легко указать множество $A$ из $2n-1$ клеток, удары по которым позволяют найти любое $K$ (пример для $n=10$ приведен на рисунке $1$). С другой стороны, $2n-2$ клеток заведомо недостаточно. Это следует из того, что любое множество $A$ из $2n-2$ доски $n×n$ можно разбить на два непустых подмножества $B$ и $C$, так, что ни одна из вертикалей и ни одна из горизонталей, пересекающихся с $B$, не пересекающихся с $C$ (тогда, если ответ «попал!» будет в точности на $B,$ мы не сможем узнать, горизонтальные корабли или вертикальные). Докажем это.

Сопоставим каждой горизонтали красную, а каждой вертикали — синюю точку (вершину графа) и для каждой клетки множества $A$ (на рисунке $2$ они обозначены звездочками) соединим ребром пару точек, соответствующую ее вертикали и горизонтали (рис. $2$). Мы получим граф с $2n$ вершинами и $2n-2$ ребрами. Такой граф не может быть связным (см. «Квант». 1981. №6. с. 10) — он обязательно распадается на два или больше отдельных кусков. Ребра одного из связных кусков можно принять за множество $B$ (см. рис. $2$), остальные — за множество $C$. (Разумеется, это рассуждение можно изложить и не пользуясь терминологией теории графов.) Итак, в случае $(1)$ ответ: $2n-1$.

$(2)$ Пусть корабли не имеют общих точек. Докажем, что в этом случае необходимое количество $a$ ударов — клеток в множестве $A$ — не меньше $\frac{4n}{3}$. При этом будут использованы только такие свойства множества $A$: в каждой горизонтали и вертикали встречается хотя бы одна клетка множества $A,$ и для любой клетки множества $A$ в ее горизонтали или вертикали есть еще хотя бы одна клетка $A$.

Расставим в клетках множества $A$ синие и красные единицы и двойка так: на каждой горизонтали, где клеток $A$ более одной, запишем в каждую из них красную $1$, а где лишь одна клетка — запишем в нее красную $2$; точно так же на каждой вертикали запишем в клетке множества $A$ синие $1$ и $2$ (рис. $3$). Поскольку в каждой клетке множества $A$ стоят либо единица и двойка, либо две единицы, сумма $s$ всех написанных чисел не больше $3a$. Поскольку на каждой линии (горизонтали и вертикали) мы записали числа с суммой не меньше $2$, $s\geqslant 4n$. Поэтому $a\geqslant s/3\geqslant 4n/3$.

На рисунке $4$ показано, как можно направить требуемым образом $4$ удара на доске $3×3$ ($n=3$). Используя этот «блок» $3×3$, можно построить пример направления $a$ ударов, где $a$ — наименьшее целое число, для которого $a\geqslant\frac{4n}{3}$ (примеры для $n=4$, $n=8$ и $n=10$ показаны на рисунках $3$ — $5$).

Итак, в этом случае ответ: $\left[\frac{4n+2}{3}\right]$, то есть для $n=3k$, $n=3k+1$ и $n=3k+2$ нужно соответственно $4k$, $4k+2$ и $4k+3$ ударов.

Н.Васильев