Условие

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

Н.Васильев

Задача из журнала «Квант» М641(1980, выпуск №9)

Задача:

Дан правильный шестиугольник $ABCDEF$ с центром $O$. Точки $M$ и $N$ — середины сторон  $CD$ и $DE$. Прямые  $AM$ и $BN$ пересекаются в точке $L$.

Докажите, что:

а) треугольник $ABL$ и четырехугольник $DMLN$ имеют равные площади;

б) $\widehat{ALO}=\widehat{OLN}=60^\circ$;

в) $\widehat{OLD}=90^\circ$.

Решение:

Все утверждения задачи не трудно получить из одного наблюдения: при повороте на $60^\circ$ вокруг центра $O$ четырехугольник $AMCB$ отображается на четырехугольник $BNDC$.

Действительно, при повороте $R_O^{60^\circ}$ (против часовой стрелки) точка $A$ переходит в точку $B$, точка $B$ — в точку $C$, сторона $CD$ отображается в сторону $DE$, так что середина $M$ стороны $CD$ переходит в середину $N$ стороны $DE$ (смотри рисунок). Следовательно, четырехугольники $AMCB$ и $BNDC$ конгруэнтны, так что площади их равны. Вычитая из этих равных площадей площадь четырехугольника $BCML$, получим равные площади, то есть треугольник $ABL$ и четырехугольник $DMLN$ равновелики.

Так как при повороте $R_O^{60^\circ}$ луч $AM$ отображается на луч $BN$, угол между направлениями этих лучей равен углу поворота, то есть $\widehat{ALB}=60^\circ$. Следовательно, $\widehat{ALN}=120^\circ$.Приведем два доказательства того , что $\widehat{ALO}=\widehat{OLN}=60^\circ$ и $\widehat{OLD}=90^\circ$.

$1^\circ$. Воспользуемся таким очевидным фактом: если две прямые, пересекающиеся в точке $K$, равноудалены от точки $P$, то прямая $PK$ служит биссектрисой угла между этими прямыми (содержащего точку $P$). Поскольку точка $O$ равноудалена от прямых $AM$ и $BN$, $OL$ — биссектриса угла $ALN$, то есть $\widehat{ALO}=\widehat{OLN}=60^\circ$. Поскольку точка $D$ удалена от прямых $AM$ и $BN$ одинаково (на такое же расстояние, как $C$ — от прямой $AM$). $\widehat{NLD}=\widehat{DLM}=30^\circ$, то есть $\widehat{OLD}=90^\circ$.

$2^\circ$. Около четырехугольника $DMON$ можно описать окружность, так как углы  при его вершинах $M$ и $N$ — прямые. Тогда $L$ также принадлежит этой окружности. Это следует из того, что в четырехугольнике $DMLN$ сумма углов при вершинах $D$ и $L$ равна $180^\circ$. Заметив, что $\widehat{ODN}=60^\circ$, применим теорему о вписанном угле. Тогда получим $\widehat{OLN}=\widehat{ODN}=60^\circ$ и $\widehat{OLD}-\widehat{OMD}=90^\circ$.

Э.Готман

Условие

На плоскости отмечены $2n + 1$ различных точек. Занумеруем их числами $1, 2, \ldots, 2n + 1$ и рассмотрим следующее преобразование $R$ плоскости: сначала делается симметрия относительно первой точки, затем относительно второй и т. д. — до $\left(2n + 1\right)$-й точки.

а) Покажите, что y этого преобразования $R$ есть единственная «неподвижная точка» (точка, которая отображается в себя).

Рассмотрим всевозможные способы нумерации наших $2n + 1$ точек (числами $1, 2, \ldots, 2n + 1$). Каждой такой нумерации соответствует свое преобразование плоскости $R$ и своя неподвижная точка. Пусть $F$ — множество неподвижных точек всех этих преобразований.

б) Укажите множество $F$ для $n = 1$.

в) Какое максимальное и какое минимальное количество точек может содержать множество $F$ при каждом $n = 2, 3, \ldots$

Решение

Фиксируем произвольную систему координат.

Пусть точки $A\left(x; y\right)$ и $A^*\left(x^*; y^*\right)$ симметричны относительно точки $A’\left(x’; y’\right)$. Тогда $x’ = \frac{\left(x + x^*\right)}{2}, y’ = \frac{\left(y + y^*\right)}{2},$ откуда $$x^* = 2x’ — x, y^* = 2y’ — y.$$

Таким образом, точка с координатами $\left(x; y\right)$ при симметрии относительно точки с координатами $\left(x’; y’\right)$ переходит в точку с координатами $\left(2x’ — x; 2y’ — y\right)$.

Поэтому при нашем преобразовании $R$ точка с координатами $\left(x; y\right)$ перейдет в точку с координатами $\left(-x + 2x_1 — 2x_2 + \cdots + 2x_{2n + 1}; -y + 2y_1 — 2y_2 + \cdots + 2y_{2n + 1}\right),$ где $\left(x_i; y_i\right)$ — координаты $i$-й из заданных $2n + 1$ точек.

a) Для неподвижной точки $\left(x; y\right)$ преобразования $R$ эти координаты определяются однозначно из условия $$ \begin{cases}-x + 2x_1 — 2x_2 + \cdots + 2x_{2n + 1} = x \\ -y + 2y_1 — 2y_2 + \cdots + 2y_{2n + 1} = y\end{cases}$$ и равны $\left(x_1 — x_2 + \cdots — x_{2n} + x_{2n + 1}; y_1 — y_2 + \cdots — y_{2n} + y_{2n + 1}\right)$ или $$\left(\sum_{i = 1}^{2n + 1} \left(-1\right)^{i — 1} x_i; \sum_{i = 1}^{2n + 1} \left(-1\right)^{i — 1} y_i\right) \tag{*}$$ Утверждение a) доказано.

б) Пусть сначала данные точки $X_1, X_2, X_3$ не лежат на одной прямой. Если точка $A_1$ после симметрии относительно точек $X_1, X_2, X_3$ отобразилась в себя (см. рисунок), то $X_1, X_2, X_3$ — середины отрезков $A_1A_2, A_2A_3, A_3A_1$, где $A_2 = SX_1\left(A_1\right)$, $A_3 = SX_2\left(A_2\right)$. Значит, $\left[A_1A_2\right]$, $\left[A_2A_3\right]$, $\left[A_3A_1\right]$ — медианы треугольника $A_1A_2A_3$, так что точки $A_1, A_2, A_3$ можно получить из точек $X_1, X_2, X_3$ гомотетией с центром в центре тяжести $O$ треугольника $X_1X_2X_3$ и коэффициентом $(—2)$. Этим положение точек $A_i \left(i = 1, 2, 3\right)$ определяется однозначно. С другой стороны, каждая точка $A_i$ при соответствующей композиции симметрий относительно точек $X_i$, отображается в себя (например, $SX_2\left(SX_1\left(SX_3\left(A_3\right)\right)\right) = A_3$). Поэтому множество $F$ — это три точки, получающиеся из данных точек $X_1, X_2, X_3$ гомотетией с центром $O$ и коэффициентом $(-2)$. Легко видеть, что, если данные точки $X_1, X_2, X_3$ лежат на прямой, ответ получается, в разумном смысле, тот же.

в) Глядя на выражение $(*)$, нетрудно сообразить, что в множестве $F$ точек не больше, чем число способов выбрать из $2n + 1$ данных точек те $n$ точек, перед абсциссами которых в выражении $(*)$ будет стоять знак «минус», то есть не больше, чем $C^n_{2n + 1}$. Очевидно, эта оценка точна (возьмите, например, $2n + 1$ точек на одной прямой с целыми координатами $1, 2, 2^2, \ldots, 2^{2n}$).

Оценим теперь число неподвижных точек снизу. Спроектируем данные $2n + 1$ точек на прямую так, чтобы никакие две точки не попали в одну. На этой прямой введем координаты и перенумеруем точки в порядке возрастания координат: $x_1 < x_2 < \ldots < x_{2n + 1}$. Поставим $n$ минусов перед первыми $n$ числами и рассмотрим сумму $- x_1 — x_2 — \cdots — x_n + x_{n + 1} + \cdots + x_{2n + 1}$: она будет соответствовать некоторой неподвижной точке из нашего множества $F$. Далее произведем следующую операцию: выберем пару чисел $x_i$ и $x_{i + 1}$ таких, что перед $x_i$ стоит минус, а перед $x_{i + 1}$ — плюс, и поменяем у них знаки (на первом шаге, очевидно, $i = n$). Каждая такая операция приводит к сумме, соответствующей неподвижной точке из множества $F$, причем, поскольку после каждой такой операции сумма уменьшатся, все эти неподвижные точки различны. Всего таких операций (вне зависимости от их порядка) мы можем произвести $n\left(n + 1\right)$, что уже даст нам $n\left(n + 1\right) + 1$ неподвижных точек. Значит, в $F$ точек не меньше $n\left(n + 1\right) + 1$. Ровно столько неподвижных точек получится, если, например, снова взять $2n + 1$ точек на прямой с целыми координатами $-n, -\left(n — 1\right), \ldots, -1, 0, 1, 2, \ldots, n — 1, n$. При всевозможных способах расстановки $n$ «минусов» перед некоторыми из них максимальное значение суммы этих чисел равно $2 \cdot \left(1 + 2 + \cdots + n\right) = n(n + 1)$, минимальное значение равно $-n\left(n + 1\right)$, причем сумма может принимать любое четное значение между числами $-n\left(n + 1\right)$ и $n\left(n + 1\right)$ — всего $n\left(n + 1\right) + 1$ значений.

И. Клумова, А. Талалай

Задача из журнала «Квант» (1981 год, 9 выпуск)

Условие

Вокруг квадрата описан параллелограмм (вершины квадрата лежат на разных сторонах параллелограмма). Докажите, что перпендикуляры, опущенные из вершин параллелограмма на стороны квадрата, образуют новый квадрат $(рис. 1).$

Решение

Пусть вокруг черного квадрата $(см. рис. 1)$ описан голубой параллелограмм $ABCD$ и через все его вершины проведены красные прямые, перепендикулярные сторонам квадрата. Достаточно доказать, что при повороте на $90^{\circ}$ вокруг центра $O$ черного квадрата красные прямые переходят друг в друга.

                                              $ Рис. 1.$

Пусть $H = R_{0}^{90^{\circ}}(A).$ Поскольку стороны повернутого параллелограмма перпендикулярны сторонам исходного, $(HE)\perp (AB)$ и $(HF)\perp (BC).$ Поэтому $H$ — точка пересечения высот треугольника $EBF$ и, следовательно, $H$ лежит на красной прямой, проведенной через вершину $B.$ Таким образом, красная прямая, проведенная через точку $A,$ переходит при повороте $R_{0}^{90^{\circ}}$ в красную прямую, проведенную через точку $B.$ Отсюда немедленно следует утверждение задачи.

Теорема о том, что три высоты треугольника пересекаются в одной точке (мы надеемся, известная нашим читателям), не доказывается в школьном учебнике. Поэтому мы приведем еще одно решение задачи $M704,$ хотя и не столь изящное, но тоже простое.

Это решение годится и для более общего случая, когда роль квадрата играет черный параллелограмм $(рис. 2):$ мы докажем, что красные прямые (соответственно параллельные сторонам черного параллелограмма) образуют параллелограмм, гомотетичный черному параллелограмму.

                                $ Рис. 2.$

Для доказательства достаточно проверить, что красная точка $K$ (см. рисунок 3 — фрагмент рисунка 2) лежит на диагонали параллелограмма $EG.$ Из подобия заштрихованных треугольников следует, что $\frac{x}{a} = \frac{b}{v}$ и $\frac{a}{y} = \frac{u}{b}$ (обозначения см. на рисунке 3). Перемножив эти равенства, получим $\frac{x}{y} = \frac{u}{v},$ а это и значит, что точка $K$ лежит на $EG.$

                                      $ Рис. 3.$

Полученный результат напоминает теорему Паппа, которую $Д.~ Гильберт$ и $С.~ Кон-Фоссен$ в своей замечательной (переизданной недавно по-русски) книге «Наглядная геометрия» формулируют так $(с. 126—127):$ если вершины замкнутой шестизвенной ломаной лежат попеременно на двух прямых и две пары ее противоположных звеньев параллельны, то и третья пара звеньев параллельна (на рисунке 3 — как раз такая ломаная $AKBEFGA$).

На этом возможности обобщений не исчерпаны. Если «сфотографировать» конфигурацию рисунка 3 (то есть спроектировать ее из некоторой точки $S,$ не лежащей в плоскости рисунка, на непараллельную плоскость), мы получим конфигурацию Паскаля: три пары параллельных на рисунке 3 прямых будут пересекаться на «фотографии» в трех точках одной прямой — нам удобно обозначить их $A_{1},$ $F_{1}$, $B_{1}$ $(рис. 4)$ — и наша теорема о точках $E,$ $K,$ $G$ превратиться в такую теорему: если каждая тройка точек $A,$ $B,$ $F$ и $A_{1},$ $B_{1},$ $F_{1}$ лежит на прямой, то точки $(AB_{1})\cap (A_{1}B),$ $(BF_{1})\cap (B_{1}F)$ и $(AF_{1})\cap (A_{1}F)$ также лежат на прямой.                                                $Рис. 4.$

Н.Васильев