М684. Задача о новом варианте морского боя

Условие

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

Н.Васильев

М655. О чиновниках и циклах

Задача из журнала «Квант». Выпуск №11 1980 года.

М655. На столе у чиновника Министерства околичностей лежит $n$ томов Британской энциклопедии, сложенных в несколько стопок. Каждый день, придя на работу, чиновник берет из каждой стопке по одному тому и складывает взятые тома в новую стопку, затем располагает стопки по количеству томов (в невозрастающем порядке) и заполняет ведомость, в которой указывает количество томов в каждой стопке. Кроме сказанного выше, чиновник никогда ничего не делает.

а) Какая запись будет сделана в ведомости через месяц, если общее кол-во томов $n = 3, n = 6, n = 10$ (начальное расположение произвольно)

б) Докажите, что если общее число томов $n=\frac{1}{2} k (k+1),$ где $k$ — натуральное, то, начиная с некоторого дня, ведомость будет заполняться одинаковыми записями.

в) Исследуйте, что будет через много дней работы при других значениях $n.$

Решение

При $n = 3$ возможны всего три расположения:
$(1, 1, 1)$ — три стопка по одному тому;
$(3)$ — одна стопка из трех томов;
$(2, 1)$ — одна стопка из двух томов и одна стопка из одного тома.

рис. 1

Стрелки на рисунке 1 показывают, во что каждое расположение переходит на следующий день. Из рисунка видно, что, с чего бы мы не начали, не позже, чем через два дня (что записано как $T = 2$), возникает расположение $(2, 1),$ и затем оно будет повторяться. На рисунке 2 показан аналогичный граф для $n = 6.$ Число $m$ возможных расположений здесь равно $11.$ Не позже, чем через $T = 6$ дней после начала работы возникнет расположение $(3, 2, 1),$ и затем оно будет повторяться. Аналогичный граф для $n=10$ имеет $m=42$ вершины, и не позже, чем через $T=12$ дней после начала возникнет расположение $(4, 3, 2, 1),$ и затем оно будет повторяться.

рис. 2

Разумеется, далеко не каждый ориентированный граф из каждой вершины которого выходят одна стрелка, обладает единственной «конечной» вершиной, то есть не всегда, идя по его стрелкам, мы придем в одну и ту же вершину и там останемся (рис. 3). Граф может распадаться на отдельные части, не связанные между собой ни одной стрелкой, может содержать циклы. Поэтому тот факт, что при $n=\frac{1}{2} k (k+1),$ начиная с некоторого дня, получается одно и то же расположение совсем не очевиден, и мы сейчас его докажем. Рассмотрим сразу произвольное $n.$

рис. 3

Вообразим четверть бесконечного листа бумаги в клетку (рис. 4), клетки которого пронумерованы парами натуральных чисел слева направо и снизу вверх: клетка с номером $(x, y)$ стоит в столбце $x$ и в строке $y.$ Изготовим $n$ фишек и разместим их в клетках нашей бумаги следующим образом: в первом столбце столько фишек, сколько томов в первой стопке, во втором столько, сколько томов во второй стопке и т.д. Размещение фишек на рисунке 4 соответствует расположению $(8, 3, 3, 1, 1, 1).$ Преобразование, которое каждый день выполняет чиновник, можно представить в виде трах операций:

  1. Уберем фишки, находящиеся в самой нижней строке.
  2. Передвинем оставшиеся фишки на одну клетку вниз и на одну клетку вправо.
  3. Теперь выложим на бумагу убранные фишки, но не на нижнюю строку, а на самый левый столбец (освободившийся).
рис. 4

В результате этих операций рисунок 4 перейдет в рисунок 5. Правда, результат действия наших трех операций отличается от того, что делает чиновник, тем, что в конце дня чиновник еще упорядочивает стопки по убыванию, но мы пока что не будем делать таких преобразований.

При нашей последовательности операций фишка $(x, y)$ перейдет в клетку $(1, x),$ если $y = 1,$ или $(x+1,y-1),$ если $y>1.$

рис. 5

Назовем $i$-й диагональю совокупность тех клеток $(x, y),$ для которых $x+y=i+1.$ Под действие нашего преобразования фишки, находящиеся на $i$-й диагонали, не сойдут с нее, а будут перемещаться по правилу: $$(1, i)\longrightarrow(2, i-1)\longrightarrow(3, i-2)\longrightarrow…\longrightarrow(i, 1)\longrightarrow(1, i)$$

Теперь дополним преобразование, тем, что в каждой строке, где это возможно, сдвинем все фишки на одно место влево, тем самым упорядочим стопки как надо. Теперь все наше преобразование точно соответствует тому, что делает чиновник. Сдвиг влево означает, что для некоторых фишек величина $x+y$ может уменьшаться, но она по-прежнему не может увеличиваться. Но эта величина — натуральное число, значит она не может уменьшаться бесконечное количество раз. Наступит такой момент, что для всех фишек величина $x+y$ уже не будет уменьшаться. Таким образом каждая фишка займет свою диагональ. Докажем, что тогда для всякого $i$ будет выполняться следующее условие: если $i$-я диагональ не полностью заполнена фишками, то в $(i+1)$-й диагонали нет ни одной фишки.

Докажем от противного: пусть в $i$-й диагонали есть пустая клетка, а в $(i+1)$-й диагонали есть хоть одна фишка. Фишки на $i$-й диагонали (если они есть) передвигаются, попадая через каждые $i$ шагов на прежние места. фишка на $(i+1)$-й диагонали передвигается, попадая через каждые $(i+1)$ шагов на прежнее место. Посмотрим, что происходит в моменты $0, (i+1), 2(i+1), 3(i+1),…,i(i+1).$ Фишка на $(i+1)$-й диагонали в эти моменты оказывается там же, где и была в нулевой момент. Пустое место на $i$-й диагонали как бы двигается вместе с фишками, значит оно побывает на всех клетках $i$-й диагонали, а значит побывает слева от фишки на $(i+1)$-й диагонали. Но тогда эта фишка должна сдвинуться влево, что невозможно, так как мы предположили, что такие перемещения уже закончились.

Что же это за расположение фишек, при котором за неполной диагональю может идти только пустая? Если $n=\frac{1}{2} k (k+1)$, то такое расположение, очевидно, только одно: все диагонали от 1-й до $k$-й заполнены фишками, а все остальные — пустые. Это доказывает утверждение б), так как все фишки не покидают своих диагоналей, и не сдвигаются влево с какого-то момента.

Пусть теперь $n\neq\frac{1}{2} k (k+1)$. Тогда существует такое $k,$ что $$\frac{1}{2} k (k+1)<n<\frac{1}{2} (k+1) (k+2).$$

Положим $r=n-\frac{1}{2} k (k+1).$ В этом случае расположение фишек, при котором за неполной диагональю следуют пустые такое: все диагонали от 1-й до $k$-й заполнены фишками, на $(k+1)$-й диагонали находится $r$ фишек, а следующие диагонали пусты. Фишки, находящиеся на $(k+1)$-й диагонали перемещаются по ней, попадая через каждые $(k+1)$ шагов на свои прежние места. Это ответ на вопрос в).

М416. О максимальном количестве ребер в таком графе, что никакие три ребра не создают треугольник

Задача из журнала «Квант»(1977 №8)

Условие

На плоскости даны $n$ точек $A_{1},\ldots,A_{n}$, никакие три из которых не лежат на одной прямой. Какое наибольшее число отрезков с концами в этих точках можно провести так, чтобы не получилось ни одного треугольника с вершинами в этих точках?

Решение

Проведем максимальное число отрезков с концами в точках $A_{1},\ldots,A_{n}$. Получим некоторый граф с вершинами в этих точках. Отрезки с концами в вершинах графа будем называть ребрами графа. Оценим число ребер в нашем графе.

Назовем степенью вершины в графе число выходящих из неё ребер. Пусть $k$ — максимальная степень вершины в графе, и пусть некоторая вершина $A_{i}$ соединена с $k$ вершинами $A_{j_{1}},\ldots,A_{j_{k}}$ графа (рисунок 1).

kvant1

Тогда степень любой вершины из множества $\left \{ A_{j_{1}},\ldots,A_{j_{k}} \right \}$ не превосходит $n-k$ ($n$ — число вершин графа), поскольку любые вершины из этого множества уже не могут быть соединены ребром (в нашем графе никакие три ребра не образуют треугольника — с вершинами в вершинах графа). Так как $k$ — максимальная степень вершины в графе, степень каждой из оставшихся $n-k$ вершин не превосходит $k$. Поэтому сумма степеней всех вершин графа не превосходит $$k \left(n-k \right )+ \left (n-k \right) k=2k \left (n-k\right).$$ Но легко видеть, что сумма степеней всех вершин графа равна удвоенному количеству его ребер. Следовательно, количеств ребер графа не больше $$k\left(n-k\right)\leqslant\left(\frac{k+(n-k)}{2}\right)^{2}=\frac{n^{2}}{4}.$$ Чтобы получить данное соотношение, мы воспользовались теоремами о среднем арифметическом и среднем геометрическом. Учитывая, что количество ребер графа — число целое, мы получаем, что ребер в нашем графе не больше чем $\left [ \frac{n^{2}}{4}\right]$ (здесь $\left [ x \right]$ означает целую часть числа $x$ — наибольшее целое число, не превосходящее $x$).

Укажем теперь способ построения графа без треугольников с $n$ вершинами, число ребер которого в точности равно $\left [ \frac{n^{2}}{4}\right]$.

Разобьем множество точек $A_{1},\ldots,A_{n}$ на два: $\left [ \frac{n}{2} \right ]$ точек в одном множестве и $n — \left [ \frac{n}{2} \right ]$ — в другом. Соединив все точки точки первого множества с точками второго (как на рисунке 2, где $n=5$), мы получим граф, у которого не будет ни одного треугольника с вершинами в точках $A_{1},\ldots,A_{n}$.

kvant2

Число ребер в этом графе, очевидно, равно $\left [ \frac{n}{2} \right ]\left(n-\left [ \frac{n}{2} \right ]\right)$. Если $n$ — четное, то $$\left [ \frac{n}{2} \right ]\left (n-\left [ \frac{n}{2} \right ]\right)=\frac{n^{2}}{4}=\left [ \frac{n^{2}}{4} \right ].$$Если $n$ — нечетное, то $\left [ \frac{n}{2} \right ]\left(n-\left [ \frac{n}{2} \right ]\right)=$ $\frac{n-1}{2}\left(n-\frac{n-1}{2}\right)=$ $\frac{n^{2}-1}{4}=$ $\left [ \frac{n^{2}}{4}\right].$ Что и требовалось доказать.

Итак, ответ в задаче: максимальное число отрезков равно $\left [ \frac{n^{2}}{4}\right]$(этот результат в теории графов называют теоремой Турана).