Задано конечное множество $K_0$. К нему добавляются все точки, которые можно получить симметричным отражением одной точки этого множества относительно другой. Полученное множество обозначается $K_1$. Аналогично из множества $K_1$ получается $K_2$, из $K_2$ — $K_3$ и т. д.
Пусть множество $K_0$ состоит из двух точек $A$ и $B$ на расстоянии 1. При каком наименьшем $n$ в множестве $K_n$ найдётся точка, находящаяся на расстоянии 10000 от точки $A$?
Пусть $K_0$ состоит из трёх вершин правильного треугольника площадью 1. Найдите площадь наименьшего выпуклого многоугольника, содержащего множество $K_n$ ($n=1$, 2, $\ldots$).
В следующих трёх пунктах $K_0$ — множество четырёх вершин правильного тетраэдра объёма 1.
Рассмотрим наименьший выпуклый многогранник, содержащий все точки множества $K_1$. Сколько и каких граней у этого многогранника?
Чему равен объём этого многогранника?
Найдите объём наименьшего выпуклого многогранника, содержащего множество $K_n$ ($n=2$, 3, $\ldots$).
Н. Б. Васильев
Всесоюзная математическая олимпиада школьников (XII, 1978 год, 8 и 10 классы)
В этой задаче мы изучаем такую операцию над произвольной фигурой (множеством точек) $\varPhi$:
$$
W(\varPhi)=\textstyle\bigcup\limits_{M\in\varPhi}S_M(\varPhi)\tag1
$$
— рассматриваются симметричные образы фигуры $\varPhi$ относительно различных точек $M\in\varPhi$ и берётся их объединение (по всем точкам $M$). Очевидно, всегда $W(\varPhi)\supset\varPhi$ и $$
\text{если}~\varPhi\subset\varPhi'{,}~\text{то}~W(\varPhi)\subset W(\varPhi').\tag2
$$
Выяснение поставленных в условии конкретных вопросов для последовательностей вида
$$
\varPhi,~W(\varPhi),~W^2(\varPhi)=W(W(\varPhi)),~{\ldots},~W^n(\varPhi)=W(W^{n-1}(\varPhi)),
$$
полученных многократным применением операции $W$ к некоторым конечным множествам $\varPhi$, мы включим в небольшое исследование, в ходе которого мы, по существу, научимся отыскивать выпуклую оболочку фигуры $W^n(\varPhi)$ — наименьшее выпуклое множество, содержащее $W^n(\varPhi)$, — для произвольной фигуры $\varPhi$, и отметим ряд любопытных свойств операции $W$.
Прежде чем читать решение дальше, нарисуйте фигуры $W(\varPhi)$ и $W^2(\varPhi)$, если $\varPhi$ — пара точек; отрезок; прямоугольник; четыре вершины прямоугольника; три вершины треугольника. А каково $W(\varPhi)$, если $\varPhi$ — куб; восемь вершин куба?
Начнём с одномерного случая, когда фигура $\varPhi$ лежит на прямой. Этот случай нужен для решения задачи а), но, как мы увидим, он пригодится и в более трудных задачах.
Пусть сначала наша фигура — это отрезок $\varPi=[AB]$ длины $d$ с серединой в точке $O$. Тогда $W(\varPi)=[A_1B_1]$ — отрезок длины $d$ с серединой в той же точке $O$. Отсюда сразу следует, что $W^2(\varPi)=[A_2B_2]$, где $|A_2B_2|=3d$, и вообще $W^n(\varPi)=[A_nB_n]$, где $|A_nB_n|=3^nd$, причём все отрезки $[A_nB_n]$ имеют середину в той же точке $O$ (рис. 1).
Будем в дальнейшем образ фигуры $\varPhi$ имеющей центр симметрии $O$, при гомотетии с коэффициентом $k$ и центром $O$ обозначать через $k\varPhi$. Мы выяснили, что если $\varPi$ — отрезок, то $W(\varPi)=3\varPi$ и вообще
$$
W^n(\varPi)=3^n\varPi.\tag3
$$
Забегая вперёд, заметим, что это верно для любой центрально-симметричной выпуклой фигуры $\varPi$. Но прежде закончим с одномерным случаем — ответим на вопрос а).
а) Пусть $K_0=\{A,B\}$, $|AB|=1$. Согласно (2), где $\varPhi=\{A,B\}$, $\varPi=\varPhi'=[AB]$,
$$
K_n=W^n(K_0)\subset W^n(\varPi)=3^n\varPi.\tag4
$$
При этом ясно, что $K_n$ содержит все точки отрезка $[A_nB_n]=3^n\varPi$, находящиеся на целочисленном расстоянии от точки $A$, причём крайние точки $\{A_n,B_n\}=3^n\{A,B\}$ находятся от $A$ на расстояниях $\dfrac{3^n-1}2$ и $\dfrac{3^n+1}2$ (рис. 2). Поскольку эти числа (рис. 3) больше $10\,000$ при $n\ge10$, ответ на вопрос а): $n=10$.
В решении плоских и пространственных задач про операцию $W$ очень полезно такое её свойство: если $\varPhi_l$ — проекция фигуры $\varPhi$ на прямую $l$, то
$$
W(\varPhi)_l=(W(\varPhi))_l\tag5
$$
(проекция $W(\varPhi)$ на прямую $l$ совпадает с результатом применения $W$ к проекции $\varPhi_l$). Это сразу следует из определения $W$ и того факта, что при проекции точки, симметричные относительно точки $M$, попадают в точки, симметричные относительно её проекции $M_l$ (рис. 4).
Отсюда вытекает, что если $\varPi$ — полоса, а $3^n\varPi$ — её образ при гомотетии с коэффициентом $3^n$ относительно центра симметрии (какой-либо точки на средней прямой), то выполнено соотношение (3). Это верно и для «пространственной полосы» $\varPi$ — множества точек, заключённых между двумя плоскостями.
Из (2), (3), (5) и решения задачи а) следует также, что если мы заключаем фигуру $\varPhi$ в опорную полосу$\varPi$ какого-либо направления — такую полосу $\varPi\supset\varPhi$, края которой содержат все точки из $\varPhi$, — то полоса$3^n\varPi\supset W^n(\varPhi)$ будет опорной для$W^n(\varPhi)$ (рис. 5). Это соображение, обобщающее (4), позволяет найти выпуклую оболочку $W(\varPhi)$ для любой фигуры.
Разберём конкретные примеры.
б) Пусть $K_0=\{A,B,C\}$ — вершины правильного треугольника. $K_n=W^n(K_0)$, $n=1$, 2, $\ldots$ (рис. 6). Докажем, что для любого $n\ge1$ выпуклая оболочка множества $K_n$ получается так: нужно взять концы отрезков $3^n[AB]$, $3^n[BC]$ и $3^n[AC]$ и построить выпуклый шестиугольник $\textit{Ш}_n$ с вершинами в этих точках.
В самом деле, эти шесть точек — не что иное, как «крайние точки» множеств $W^n(\{A,B\})$, $W^n(\{B,C\})$, $W^n(\{C,A\})$, о которых мы говорили в задаче а). Поскольку $\{A,B\}$, $\{B,C\}$ и $\{C,A\}$ — подмножества множества $\{A,B,C\}$, согласно (2) вершины шестиугольника $\textit{Ш}_n$ принадлежат $K_n$. Следовательно, весь шестиугольник $\textit{Ш}_n$ содержится в выпуклой оболочке множества $K_n$.
С другой стороны, рассмотрев три опорные полосы $\varPi_1$, $\varPi_2$, $\varPi_3$, дающие в пересечении $\triangle ABC$, получим
$$
K_n\subset3^n\varPi_1\cap3^n\varPi_2\cap3^n\varPi_3=\textit{Ш}_n.\tag6
$$
Значит, выпуклая оболочка множества $K_n$ совпадает с $\textit{Ш}_n$.
Найдём площадь шестиугольника $\textit{Ш}_n$, считая площадь $\triangle ABC$ равной 1.
Шестиугольник $\textit{Ш}_n$ — объединение шести треугольников, из которых три подобны треугольнику $\triangle ABC$ с коэффициентом $\dfrac{3^n-1}2$, а другие три — с коэффициентом $\dfrac{3^n+1}2$, причём последние три треугольника пересекаются по треугольнику $\triangle ABC$ (рис. 6). Поэтому площадь шестиугольника $\textit{Ш}_n$ равна
$$
3\left(\dfrac{3^n-1}2\right)^2+3\left(\dfrac{3^n+1}2\right)^2-2=\dfrac{3^{2n+1}-1}2.
$$
в)—д) Пусть $K_0=\{A,B,C,D\}$, где $ABCD$ — правильный тетраэдр, $W^n(K_0)=K_n$ ($n=1$, 2, $\ldots$). Докажем, что для любого $n\ge1$ выпуклая оболочка множества $K_n$ получается так: нужно взять концы всех шести отрезков $3^n\text{Р}$, где $\text{Р}$ — произвольное ребро тетраэдра $ABCD$, и построить выпуклый многогранник $\textit{Д}_n$ с вершинами в этих 12 точках. Формальное доказательство этого факта в точности повторяет рассуждения пункта б). Что разобрать, какую форму имеет многогранник $\textit{Д}_n$, начнём со случая $n=1$.
Рис. 7
Как это часто бывает в задачах про правильный тетраэдр, удобно построить куб $L$, у которого точки $A$, $B$, $C$, $D$ — четыре несмежные вершины. Тогда 12 точек множества $K_1$ (кроме самих точек $K_0=\{A,B,C,D\}$) лежат на рёбрах гомотетичного куба $3L$, причём каждая из 12 точек делит своё ребро в отношении $1:2$, считая от вершин $A_1$, $B_1$, $C_1$, $D_1$ куба $3L$, гомотетичных вершинам $A$, $B$, $C$, $D$ куба $L$. Ясно, что многогранник $\textit{Д}_1$ получается из куба $3L$ отрезанием от каждой вершины куба «уголка»-пирамиды плоскостью, проходящей через три точки, отмеченные на рёбрах, выходящих из этой вершины (рис. 7). Пусть длина ребра тетраэдра $ABCD$ равна $a$ (т. е. длина ребра куба $L$ равна $\dfrac a{\sqrt2}$). Полученный многогранник $\textit{Д}_1$ будет
иметь такие 14 граней: 6 прямоугольников $a\times2a$ (на гранях куба $3L$) и 8 правильных треугольников (оснований «пирамидок»): четыре со стороной длины $a$
и четыре со стороной длины $2a$.
Найдём объём многогранника $\textit{Д}_1$, считая объём тетраэдра $ABCD$ равным 1. Заметим, что плоскость, проходящая через три несмежные вершины куба, отрезает от него пирамиду, объём которой составляет $\dfrac16$ объёма куба. Таким образом, объём тетраэдра $ABCD$ составляет $\dfrac13$ объёма куба $L$, т. е. объём куба $L$ равен 3, объём куба $3L$ равен 81, объём отрезаемых пирамидок — $4\cdot\dfrac12+4\cdot4=18$; поэтому объём $\textit{Д}_1$ равен 63.
Многогранник $\textit{Д}_n$ для любого $n\ge1$ имеет точно такое же строение, как $\textit{Д}_1$, но другие размеры граней; его 12 вершин лежат на рёбрах куба $3^nL$ и делят их (считая от вершин, гомотетичных $A$, $B$, $C$, $D$) в отношении $(3^n-1):(3^n+1)$. Эти вершины, очевидно, принадлежат $K_n$.
Доказательство того, что $K_n\subset\textit{Д}_n$, аналогично (6): существует семь пространственных полос $\varPi_i$, края каждой из которых содержат четыре точки $K_0$ (три из этих полос дают в пересечении куб $L$, а остальные четыре дают в пересечении тетраэдр $ABCD$), и $\bigcap\limits_{i=1}^73^n\varPi_i=\textit{Д}_n$. Объём многогранника $\textit{Д}_n$ находится так же, как объём многогранника $\textit{Д}_1$ — он равен
$$
3^{3n+1}-4\cdot\left(\dfrac{3^n-1}2\right)^3\cdot\dfrac12-4\cdot\left(\dfrac{3^n+1}2\right)^3\cdot\dfrac12=\dfrac{5\cdot3^{3n}-3^{n+1}}2.
$$
Таким образом, при большом $n$ многогранник $W^n(\varPhi)$ по форме приближается к полуправильному многограннику кубооктаэдру — выпуклой оболочке 12 середин рёбер куба (чтобы придать этим словам точный смысл, удобно ввести «нормирующий множитель» $\dfrac1{3^n}$ и говорить о предельном поведении многогранника, гомотетичного $W^n(\varPhi)$ с коэффициентом $\dfrac1{3^n}$; см. ниже пункт 4).
Заметим, что, как и в задаче б), в пространственной задаче не существенно, что тетраэдр $ABCD$ правильный; это удобно лишь тем, что все фигуры получаются симметричными (в общем случае вместо куба мы имели бы параллелепипед и т. д.).
Перечислим в заключение ещё несколько общих свойств «операции $W$» (о некоторых из них нам сообщили в письмах по поводу решения задачи M515).
1. В задаче б) $\textit{Ш}_n=W^n(\triangle ABC)$, в следующих пунктах $\textit{Д}_n=W^n(\text{тетраэдр}~ABCD)$. Вообще, если обозначить выпуклую оболочку фигуры $\varPhi$ через $\mathscr{B}(\varPhi)$, то $\mathscr{B}(W(\varPhi))=W(\mathscr{B}(\varPhi))$. В частности, если фигура $\varPhi$ — выпуклая, то $W(\varPhi)$ — тоже. Это можно доказать, используя такое определение операции $W$ на языке векторов:
$$
W(\varPhi)=\{M''\colon\overrightarrow{OM''}=2\overrightarrow{OM}-\overrightarrow{OM'}{;}~
M,M'\in\varPhi\}
$$
(здесь $O$ — любая фиксированная точка).
Будем далее считать $\varPhi$ выпуклой фигурой.
2. Если $\varPhi$ — центрально-симметричная фигура с центром $O$, то $W(\varPhi)=3\varPhi$ и вообще $W^n(\varPhi)=3^n\varPhi$.
3. Для любого $n$ фигуру $W^n(\varPhi)$ можно получить как пересечение полос $3^n\varPi$, где $\varPi$ — всевозможные опорные полосы для $\varPhi$ (различных направлений); при этом если $\varPhi$ — многоугольник на плоскости, то можно ограничиться рассмотрением полос $\varPi$, края которых содержат по крайней мере три (для многогранника $\varPhi$ — четыре) его вершины.
4. При $n\to\infty$ существует предел $S^*(\varPhi)$ фигуры, гомотетичной $W^n(\varPhi)$ с коэффициентом $\dfrac1{3^n}$ и некоторым центром $O$ (надо ещё определить, что значит расстояние между фигурами! См. по этому поводу книгу Д. О. Шклярского, Н. Н. Ченцова и И. М. Яглома «Геометрические оценки и задачи из комбинаторной геометрии» (М., Наука, 1974), с. 14—17). Эту предельную фигуру можно получить как пересечение всех опорных полос фигуры $\varPhi$, сдвинутых параллельно так, чтобы точка $O$ была их общим центром симметрии, или — как множество $\left\{M^*\colon\overrightarrow{OM^*}=\dfrac12(\overrightarrow{OM}-\overrightarrow{OM'}){;}~M,M'\in\varPhi\right\}$. Фигура $S^*(\varPhi)$ центрально-симметрична и выпукла. Её называют иногда симметризацией Минковского фигуры $\varPhi$. О её свойствах см. задачу 57 в книге В. Г. Болтянского и И. М. Яглома «Выпуклые фигуры» (М., ГТТИ, 1951).
