Освещение плоскости прожекторами

28

В. Гальперин, Г. Гальперин

Овсешение плоскости проекторами

Интересная и трудная задача М545, решение которого посвязывана эта заметка, по постановке вопроса и методам решения типична для комбинаторной геометрии — раздела геометрии, занimaющeresя задачи о разбиениях, покрытиях, упаковках фигур.
Напомним ее формулировку:

На плоскости задано n точек. Нужно разместить в этих точках n проекторов, каждый из которых освещает угол величины $\frac{360^\circ}{n}$ так, чтобы освещать всю плоскость. Докажите, что это возможно при любом расположении данных точек, если a) n=3; 6) n=4; в) n — любое натуральное число (в случае a) — в) проекторы можно поворачивать); г) Пусть теперь проекторы освещают углы $a_1, a_2, \dots, a_n$ ($a_1 + a_2 + \dots + a_n = 360^\circ$) и составлены в одну точку так, что они освещают всю плоскость. Докажите, что можно перевести*) в каждую из данных точек по одному из n проекторов так, что все плоскость будет по-прежнему освещена.

История этой задачи достаточно интересна. Самый простой ее частный случай 6) представляется на первой Всесоюзной математической оптимизации в 1967 году. Именно там с ней познакомился второй из авторов этой заметки (тогда он еще был школьником). Несколько лет спустя он нашел доказательство более

*) Имеется в виду, что проекторы можно параллельно переносить, но не поворачивать!

Рассмотрим теперь углы, симметричные этим углам относительно точки O. На рисунке 2 показано, как направить проектор, помещенный в точку $M_1$ так, чтобы он освещал закрашенный красным цветом угол. Аналогично, проекторы в точках $M_2$ и $M_3$ можно направить так, чтобы они освещали «свой» углы.

Ту же идею — разделить плоскость на части. Так, чтобы каждую из них удалость освещить своей группой проекторов, — можно применить в случае в).

Для этого достаточно доказать следующее два утверждения.

Утверждение 1. Пусть внутри данной угла величины $\alpha = k \frac{2\pi}{n}$, где $k \leqslant \frac{n}{2}$ расположен k проекторов. Тогда их можно повернуть так, чтобы они вместе освещили целиком угол, симметричный данному относительно его вершины (рис. 3).

Для доказательства этого утверждения индикцией по k удобно использовать такую арифметическую лемму. Если $s_1, s_2, \dots, s_k$ — целые неотрицательные числа, причем $s_1 \geqslant 1$,

Рис. 1.
Рис. 2.

29

$s_k \geq 1$ и $s_1 + s_2 + \dots + s_k = k$, то существует $m < k$, для которого $s_1 + \dots + s_m = m$ (тое $s_{m+1} + \dots + s_k = k - m$).

Наконец, остается доказать еще такой довольно очередный факт — легче сделать это отдельно для четного и для нечетного $n$.

Утверждение 2. Если в плоскости задано $n$ точек $A_1, A_2, \dots, A_n$, то ее можно разбит на две полуплоскости, содержащие по $n/2$ точек, если $n$ четно, или на три угла с общей вершиной и величины $k_1, k_2, \frac{2\pi}{n}, k_3, \frac{2\pi}{n}$, где $k_1 + k_2 + k_3 = n$ и $k_i < n/2$ ($i=1, 2, 3$), каждый из которых содержит по $k_i$ точек, если $n$ нечетно.

Упражнение 1. Докажите утверждение 1, лемму и утверждение 2.

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

Алгоритм улушення

Наметим идею решения пункта. Г). Расставим проекторы по данным точкам $M_1, M_2, \dots, M_n$ произвольным образом. Если при этом не все плоскость освещена, мы предъявим другой, «улушенный» способ расстановки проекторов (при этом «качество» расстановки будет оцениваться неокторой числовой функцией $f$). Поскольку всего расстановок проекторов по точкам $M_1, M_2, \dots, M_n$ лишь конечное число (равное $n!$), взяв расстановку, для которой значение функции $f$ максимально, мы автоматически освещим полностью все плоскость: действительно, если бы при этом не все плоскость освещалась, мы смогли бы еще «улушить» расстановку, получив тем самым противоречие.

Начем реализовать этот план. Тепер проекторы — любые углы $a_i$ с общей вершиной $O$, $0 < a_i < \pi$, $a_1 + a_2 + \dots + a_n = 2\pi$, причем каждый из них освещает изучтри сторону неокторого выпуклого $n$-угольника $A_1A_2\dots A_n$ (рис. 4), $A_i \overrightarrow{OA_{i+1}} = a_i$. Опустим из точки $O$ перpendикularы $OH_i$ на стороны многоугольника (или их продления); пусть $|OH_i| = h_i$.

Рассмотрим векторы $\vec{e}_i = \frac{1}{h_i} \overrightarrow{OH_i}$. Ясно, что $|\vec{e}_i| = \frac{1}{h_i}$ (рис. 5).

Расстановке проекторов по точкам $M_1, M_2, \dots, M_n$ отвечает расстановка векторов $\vec{e}_1, \vec{e}_2, \dots, \vec{e}_n$ по этим точкам (мы как бы прикрепляем вектор $\vec{e}_i$ к проектору $a_i$ и переставляем их вместе как единое целое).

Единственный геометрический факт, нужный нам в дальнейшем и «оправдывающий» страный, на первый взгляд, выбор векторов $\vec{e}_i$, состоит в следующем:

Лемма. Пусть проектор $a_p$, помещенный в точку $M$, освещает точку $N$, а проектор $a_q$ — нет. Тогда $\overrightarrow{MN} \cdot \vec{e}_p > \overrightarrow{MN} \cdot \vec{e}_q$.

Доказательство. Пусть $\overrightarrow{MN} = \vec{v}$. Отложим от точки $O$ вектор $\overrightarrow{OP} = \vec{v}$ (рис. 6). Луч [OP] пересекает $p$-ю сторону многоугольника $A_1A_2\dots A_n$ в неокторой точке $K$, а $q$-ю сторону не пересекает, расстоялу проектора $s_k \geq 1$ и $s_1 + s_2 + \dots + s_k = k$, то существует $m < k$, для которого $s_1 + \dots + s_m = m$ (тое $s_{m+1} + \dots + s_k = k - m$).

Наконец, остается доказать еще такой довольно очередный факт — легче сделать это отдельно для четного для нечетного $n$.

Утверждение 2. Если в плоскости задано $n$ точек $A_1, A_2, \dots, A_n$, то ее можно разбит на две полуплоскости, содержащие по $n/2$ точек, если $n$ четно, или на три угла с общей вершиной и величины $k_1, k_2, \frac{2\pi}{n}, k_3, \frac{2\pi}{n}$, где $k_1 + k_2 + k_3 = n$ и $k_i < n/2$ ($i=1, 2, 3$), каждый из них освещает изучтри сторону неокторого выпуклого $n$-угольника $A_1A_2\dots A_n$ (рис. 4), $A_i \overrightarrow{OA_{i+1}} = a_i$. Опустим из точки $O$ перpendикularы $OH_i$ на стороны многоугольника (или их продления); пусть $|OH_i| = h_i$.

Рассмотрим векторы $\vec{e}_i = \frac{1}{h_i} \overrightarrow{OH_i}$. Ясно, что $|\vec{e}_i| = \frac{1}{h_i}$ (рис. 5).

Рис. 6.

жектор $a_p$ освещает точку $N$, а проектор $a_q$ не освещает.

Есть две возможность: 1) луч [OP] не пересекается с прямой, на которой лежит $q$-я сторона, и 2) луч [OP] пересекает эту прямую в неокторой точке $R$.

В первом случае очень важно, так как $\vec{v} \cdot \vec{e}_p > 0$, а $\vec{v} \cdot \vec{e}_q \leq 0$.

Во втором случае очень важно, так как $\vec{v} \cdot \vec{e}_p > 0$, а $\vec{v} \cdot \vec{e}_q \leq 0$.

Луч [OP] пересекает $p$-ю сторону многоугольника $A_1A_2\dots A_n$ в неокторой точке $K$, а $q$-ю сторону не пересекает, расстоялу проектора $s_k \geq 1$ и $s_1 + s_2 + \dots + s_k = k$, то существует $m < k$, для того чтобы они освещались по $n/2$ точек, если $n$ четно, или на три угла с общей вершиной и величины $k_1, k_2, \frac{2\pi}{n}, k_3, \frac{2\pi}{n}$, где $k_1 + k_2 + k_3 = n$ и $k_i < n/2$ ($i=1, 2, 3$), каждый из них освещает изучтри сторону неокторого выпуклого $n$-угольника $A_1A_2\dots A_n$ (рис. 4), $A_i \overrightarrow{OA_{i+1}} = a_i$. Опустим из точки $O$ перpendикularы $OH_i$ на стороны многоугольника (или их продления); пусть $|OH_i| = h_i$.

Рассмотрим векторы $\vec{e}_i = \frac{1}{h_i} \overrightarrow{OH_i}$. Ясно, что $|\vec{e}_i| = \frac{1}{h_i}$ (рис. 5).

30

Введем теперь величины $f_{\sigma}(N)$, зависимости от точки $N$ плоскости и от расстановки $\sigma$ проекторов по точкам $M_1, M_2, \dots, M_n$, следующим образом:

$$f_{\sigma}(N) = \overrightarrow{M_1} N \cdot \overrightarrow{e_{\sigma(1)}} + \overrightarrow{M_2} N \cdot \overrightarrow{e_{\sigma(2)}} + \dots + \overrightarrow{M_n} N \cdot \overrightarrow{e_{\sigma(n)}}$$

(1) ($\sigma(i)$ — номер проектора, поставленного, в точку $M_i$).

Следующое основное утверждение показывает, что функция $f_{\sigma}(N)$ может характеризовать «качество» расстановки.

Утверждение 3. Если точка $N$ при расстановке $\sigma$ не освещена, то найдется расстановка проекторов т такая, что $f_{\tau}(N) > f_{\sigma}(N)$.

Доказательство. Приведем сначала алгоритм, позволяющий «улучшить» расстановку $\sigma$.

Пусть проектор $\alpha_i$ расположен в точке $M_i$. Пусть проектор $\alpha_1$, стоящий в точке $M_1$, не освещает точку $N$. Уберем его на время, а в точку $M_1$ пересечем проектор, который после переосветит точку $N$.

Упражнение 2. Докажите, что такой проектор найдется.

Пусть это будет проектор $\alpha_2$. Тепер в точке $M_2$, где стоял проектор $\alpha_2$, ничего нет. Поставим в эту точку один из $n-1$ оставшихся проекторов, который после этого осветит точку $N$. Пусть это будет проектор $\alpha_3$. Поместим теперь в точку $M_3$ проектор $\alpha_4$, который после этого осветить $N$, в точку $M_4$ поместим проектор $\alpha_5$ и так далее, до тех пор, пока не образуется цикл (рис. 7): это означает, что в точку $M_k$ пересечен проектор $\alpha_{k+1}$, в точку $M_{k+1}$ — проектор $\alpha_{k+2}$, в точку $s$ — проектор $\alpha_k$ ($s > k$). Проекторы $\alpha_1, \alpha_2, \dots, \alpha_{k-1}$ возвратим на свои старые места (в точки с теми же номерами). В результате точка $N$ оказется освещенной каждой проектором $\alpha_k, \alpha_{k+1}, \dots, \alpha_s$ (так как раны точка $N$ не освещалась, $s \geq k+1$).

Посмотрим, как изменилось число $f(N)$. Слагаемые с номерами, отличными от $k, k+1, \dots, s$, в сумме (1) не изменились. А из леммы следует, что все слагаемые с номерами $k, k+1, \dots, s$ после указанной перестановки увеличились.

Итак, утверждение 3 доказано. Правда, величины $f_{\sigma}$ еще нельзя непредседательно использовать для оценки «качества» расстановки $\sigma$ — ведь она зависит от точки $N$. Здесь дело с спасает замечательное.

Утверждение 4. Для любых двух точек $N_1$ и $N_2$ разность $f_{\sigma}(N_1) - f_{\sigma}(N_2)$ не зависит от расстановки проекторов.

Доказательство. $f_{\sigma}(N_1) - f_{\sigma}(N_2) = \sum_{i=1}^{n} \overrightarrow{M_{\sigma(i)}} N_1 \cdot \overrightarrow{e_{\sigma(i)}} - \sum_{i=1}^{n} \overrightarrow{M_{\sigma(i)}} N_2 \cdot \overrightarrow{e_{\sigma(i)}} = \sum_{i=1}^{n} (\overrightarrow{M_{\sigma(i)}} N_1 - \overrightarrow{M_{\sigma(i)}} N_2) \cdot \overrightarrow{e_{\sigma(i)}} = \sum_{i=1}^{n} \overrightarrow{N_2} N_1 \cdot \overrightarrow{e_{\sigma(i)}} = c$.

Сумма $\sum_{i=1}^{n} \overrightarrow{e_{\sigma(i)}}$ есть постоянный вектор (не зависит от расстановки), $N_2 N_1$ — также фиксированный вектор, и поэтому число $c$ не зависит от расстановки проекторов, что и требовалось доказать.

Это означает, что функцию $f_{\sigma}(N)$ можно заменить функцией $f_{\sigma} = f_{\sigma}(N) + \overrightarrow{N_0} \cdot \overrightarrow{e_{\sigma(i)}} = \sum_{i=1}^{n} \overrightarrow{M_{\sigma(i)}} N_0 \cdot \overrightarrow{e_{\sigma(i)}}$, где $N_0$ — произвольная фиксированная точка плоскости.

Число $f_{\sigma}$ уже не зависит от точки $N$ и при каждой описанной нами перестановке будет возрастать.

Идея, таким образом, полностью осуществлена: найдена «функция качества», зависшая только от расстановки проекторов, и показано, как увеличить ее значение, если какая-нибудь точка не освещена. Так как неокторой расстановки $\omega$ число $f_{\omega}$ максимально, при расстановке $\omega$ освещена все плоскость.

Упражнение 3. Проведите доказательство пространственных вариантов задачи о проекторах.

а) В 8 любых точках пространства можно расположить оканты (трехгранные углы с прямыми плоскими углами (см. рис. 8, а)) так, чтобы они покрыли все пространство.

б) Пусть в пространстве заданы выпуклый многогранник с гранями $\Gamma_1, \Gamma_2, \dots, \Gamma_n$ и точка $O$ внутри него, а также $n$ точек $M_1, M_2, \dots, M_n$. Каждая грань $\Gamma_i$ определяет многогранный угол $\alpha_i$ с вершиной в $O$. В точке $O$ расположено $n$ проекторов, причем $i$-й проектор, $1 \leq i \leq n$, освещает многогранный угол $\alpha_i$ (тем самым все пространство полностью освещено (рис. 8, б)). Докажите, что проекторы можно перести в точки $M_1, M_2, \dots, M_n$ так, что все пространство по-прежнему будет освещено.