Условие

Двое играют в следующий вариант «морского боя». Один игрок располагает на доске $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$ ударов.

Н.Васильев

Два подмножества множества натуральных чисел назовем конгруэнтными, если одно получается из другого сдвигом на целое число. (Например, множества четных и нечетных чисел конгруэнтны.) Можно ли разбить множество натуральных чисел на бесконечное число (непересекающихся) бесконечных конгруэнтных подмножеств?

Ответ

Предположим, что задача уже решена. Пусть $A$ — то из множеств разбиения, которое содержит единицу. Остальные множествa разбиения получаются из $A$ сдвигами на некоторые натуральные числа, множество которых, дополненное нулем, мы обозначим через $B$. Пусть для каждого $b\in B$ множество $A_{b}$ — результат сдвига множества $A$ на $b,$ то есть множество всех чисел вида $a+b,$ где $a\in A$. По условию, если $b_{1}\neq b_{2},$ то $A_{b_{1}}\cap A_{b_{2}}=\oslash$ и всякое натуральное число $n$ принадлежит одному из множеств $A_{b},$ то есть каждое натуральное число единственным образом представляется в виде суммы $n=a+b$.

Построение множеств $A$ и $B$ мы осуществим двумя способами.

Первый способ. Пусть множества $A$ и $B$. обладающие свойством $n=a+b$ построены. Поставим в соответствие каждому натуральному числу $n=a+b$ точку плоскости $Oxy$ с координатами $\left ( a;b \right )$.

Пусть $M$ — множество всех полученных точек плоскости. Множество $M,$ очевидно, обладает следующими свойствами:
1. если $A$ — проекция множества $M$ на ось $Ox,$ а $B$ — проекция $M$ на ось $O,y$ то множество $M$ совпадает со всем множеством пар $\left ( a;b \right )$.
2. пересечение множества $M$ с каждой прямой $x+y=n$ состоит из единственной точки: в частности, при $n=1$ — это точка $\left ( 1;0 \right )$.

Ясно, что, построив хотя бы одно множество $M$ обладающее свойствами 1) и 2), мы получим нужное разбиение множества натуральных чисел.

Множество $M$ построим как объединение множеств $M_{0}\subset M_{1}\subset M_{2}\subset …\subset M_{n}\subset \ldots,$ которые, в свою очередь, будем строить так:

Пусть $M_{0}=\left \{ \left ( 1;0 \right ) \right \}$. Назовем $n$-ой диагональю прямую $x+y=n$. Точка $\left ( 1;0 \right )$ попадает на первую диагональ: вычеркнем ее и в дальнейшем, строя множества $M_{1}$ будем последовательно вычеркивать диагонали, на которые попадают построенные точки.

Сдвинем множество $M_{0}$ на единицу вправо и положим $M_{1} = \left \{ \left ( 1;0 \right ), \left ( 2;0 \right ) \right \}$ при этом вычеркнем вторую диагональ(Рис.1). Затем сдвинем множество $M_{1}$ на две единицы вверх и присоединим полученные точки к $M_{1}$: это будет множество $M_{2}$: при этом вычеркнем третью и четвертую диагонали.

Множество $M_{2}$ сдвинем на четыре единицы вправо — так, чтобы вычеркнуть следующие четыре диагонали: получим множество $M_{3}$

Вообще. множество $M_{k+1}$ строим так: сдвигаем множество $M_{k}$ на $2^{k}$ единиц вправо или вверх — так, чтобы вычеркнуть диагонали с номерами $2^{k} + 1, 2^{k} + 2, 2^{k+1}$.

Легко видеть, что объединение множеств $M_{0}, M_{1},\ldots M_{n}\ldots$ обладает свойствами 1) и 2).

Второй способ. Как известно всякое натуральное число $n$ представляется в виде $$n=a_{0}\cdot 2^{k}+a_{1}\cdot 2^{k-1}+\ldots+a_{k-1}\cdot 2+a_{k},$$ где $a_{i}$ равно 0 или 1. причем такое представление единственно. На этом основана двоичная запись числа $n$: $n_{2} = \overline{a_{0}a_{1}\ldots a_{k-1}a_{k}}$

Рассмотрим теперь два множества натуральных чисел: множество $A,$ состоящее из чисел, в двоичной записи которых единица находится в нечетных разрядах, и множество $B$ состоящее из 0 и чисел, в двоичной записи которых единица находится в четных разрядах.

Очевидно, любое натуральное $n$ единственным образом представляется в виде суммы $n=a+b$.

Множества $A$ и $B$ обладают свойством $n=a+b$. и поэтому множества $A_{b}$ дают нужное разбиение.