Двое играют в следующий вариант «морского боя». Один игрок располагает на доске $n\times n$ некоторое количество непересекающихся «кораблей» $n\times 1$ (быть может, ни одного). Второй игрок наносит одновременно ряд ударов по полям доски и про каждое поле получает от противника ответ — попал или промахнулся. По какому минимальному количеству полей следует нанести удары, чтобы по ответам противника можно было однозначно определить расположение всех его кораблей? Рассмотрите три случая:
Как показывают письма читателей, формулировка задачи допускает два одинаково осмысленных толкования — в зависимости от того, какие корабли считать «непересекающимися»:
те, которые не имеют общих клеток;
те, которые вообще не имеют общих точек, даже граничных — как это принято в обычной игре «морской бой», в которую все мы играли в детстве.
Обе задачи получились довольно интересными, хотя (1), пожалуй, попроще. С неё мы и начнём.
(1) Пусть корабли заполняют произвольное множество $K$ из нескольких горизонталей или вертикалей доски $n\times n$; мы должны указать множество $A$ из возможно меньшего числа клеток такое, что пересечение $A\cap K$ однозначно определяет множество $K$. (Заметим, что если корабли заполняют все $n$ горизонталей или все $n$ вертикалей, то они занимают все клетки доски, и мы, разумеется, никак не сможем узнать, горизонтальные корабли или вертикальные.)
Рис. 1
Легко указать множество $A$ из $2n-1$ клеток, удары по которым позволяют найти любое $K$ (пример для $n=10$ приведён на рисунке 1). С другой стороны, $2n-2$ клеток заведомо недостаточно. Это следует из того, что любое множество $A$ из $2n-2$ клеток доски $n\times n$ можно разбить на два непересекающихся подмножества $B$ и $C$ так, что ни одна из вертикалей и ни одна из горизонталей, пересекающих $B$, не пересекает $C$ (тогда, если ответ «попал!» будет в точности на $B$, мы не сможем узнать, горизонтальные корабли или вертикальные). Докажем это.
Рис. 2
Сопоставим каждой горизонтали красную, а вертикали — синюю точку (вершину графа) и для каждой клетки множества $A$ (на рисунке 2 они обозначены звёздочками) соединим ребром пару точек, соответствующую её вертикали и горизонтали (рис. 2). Мы получим граф с $2n$ вершинами и $2n-2$ рёбрами. Такой граф не может быть связным (см. «Квант», 1981, № 6, с. 10) — он обязательно распадается на два или больше отдельных куска. Рёбра одного из связных кусков можно принять за множество $B$ (см. рис. 2), остальные — за множество $C$. (Разумеется, это рассуждение можно изложить и не пользуясь терминологией теории графов.) Итак, в случае (1) ответ:$2n-1$.
(2) Пусть корабли не имеют общих точек. Докажем, что в этом случае необходимое количество $a$ ударов — клеток в множестве $A$ — не меньше $\dfrac{4n}3$. При этом будут использованы только такие свойства множества $A$: в каждой горизонтали и вертикали встречается хотя бы одна клетка множества $A$, и для любой клетки множества $A$ в её горизонтали или вертикали есть ещё хотя бы одна клетка $A$.
Расставим в клетках множества $A$ синие и красные единицы и двойки так: на каждой горизонтали, где клеток $A$ более одной, запишем в каждую из них красную 1, а где лишь одна клетка — запишем в неё красную 2; точно так же на каждой вертикали запишем в клетки множества $A$ синие 1 и 2 (рис. 3). Поскольку в каждой клетке множества $A$ стоят либо единица и двойка, либо две единицы, сумма $s$ всех написанных чисел не больше $3a$. Поскольку на каждой линии (горизонтали и вертикали) мы записали числа с суммой не меньше 2, $s\ge4n$. Поэтому $a\ge \dfrac s3\ge\dfrac{4n}3$.
Рис. 3Рис. 4Рис. 5
На рисунке 4 показано, как можно направить требуемым образом 4 удара на доске $3\times3$ ($n=3$). Используя этот «блок» $3\times3$, можно построить пример направления $a$ ударов, где $a$ — наименьшее целое число, для которого $a\ge\dfrac{4n}3$ примеры для $n=4$, $n=8$ и $n=10$ показаны на рисунках 3 и 5).
Итак, в этом случае ответ:$\left[\dfrac{4n+2}3\right]$, т. е. для $n=3k$, $n=3k+1$ и $n=3k+2$ нужно соответственно $4k$, $4k+2$, $4k+3$ ударов.
