Многоугольники на клетчатой бумаге

38

Многогуольники на клетчатой бумаге

Можно ли нарисовать на клетчатой бумаге многогуольник данной формы, помещая при этом все его вершины в узлы сетки? Как правило — нельзя. Например, из правильных многогуольников так можно нарисовать лишь квадрат. А для каких многогуольников это можно сделать приближенно, т. е. помещая вершины сколь уголно близко от узлов? Оказывается — для всех.
В этой заметке, написанной школьниками, показано, почему и как это можно сделать.

Пусть $\vec{a}$ и $\vec{b}$ ненулевыые и неоклинеарные векторы, $O$ — некоторая точка; тогда множество $\Pi$ всех таких точек

Рис. 1.

Рис. 2.

Рис. 3.

Рис. 4.

39

Более того, в статье А. Егорова доказано *), что никакие правильные многоугольники, кроме треугольника, квадрата и шестугольника — неписываются ни в какую решетку. Понятно также, что наперед заданный многоугольник произвольной формы, как правило, неписывается ни в какую решетку.

Раз задача о вписывании многоугольников в решетку приводит в большинстве случаев к отрицательному результату, естественно ее ослабить: требовать, чтобы вершины попадали в узлы лишь приближeno. Дадим точное определение:

Многоугольник ε-присывается в решетку Π, если существует подобный ему (с натуральным коэффициентом подобия) многоугольник, каждой вершина которого находится на расстоянии, меньше ε, от одного из узлов решетки (рис. 5). Заметим, что при ε = 0 здесь получается определение вписанности, данное выше, а при больших ε (болееших, чем расстояние между узлами) определение бессодержательно.

Столь же бессодержательно оно стало бы, если мы сначала бы условие натуральности коэффициента подобия; взяв этот коэффициент достаточно близким к 0, можно было бы уменьшить весь многоугольник вблизи одного узла решетки. При натуральном же коэффициente подобия (и достаточно малом ε) любые две вершины многоугольника, очевидно, не смогут попасть в ε-окрестность одного и того же узла.

Далее, мы будем говорить, что многоугольник почищаемся в

*) «Квант», 1974, № 12, c. 30.

Рис. 5.

Рис. 6.

40

Рис. 7.

и $\{n\sqrt{3}\}$, где $m > n$ — натуральные числа. Тогда $(m-n)\sqrt{3}$ отличается от целого менее чем на $\frac{1}{N}$ и следовательно, менее чем на $\varepsilon$. Положив $k$ равным $m-n$, получим требуемое.

Теорема доказана, однako имеет место значительное больше общий факт.

Основая теорема. Лобой многоугольник почини вписывается в любую решетку.

Заметим, что пункт в) задачи М475 является частным случаем этой теоремы.

Доказательство. Пусть дана решетка $\Pi$, число $\varepsilon > 0$ и многоугольник $\Phi$.

Докажем, что при неокоторой гомотетии с натуральным коэффициентом $N$ многоугольник $\Phi$ перейдет в многоугольник $\Phi'$ такой, что все вершины $\Phi'$ будут на расстоянии, меньше $\varepsilon$, от узлов решетки.

Рассмотрим вершину $A$ многоугольника. Пусть при гомотетии с центром $O$ и коэффициентом $k$ точка $A$ переходит в $A_k$ и $\overrightarrow{OA} = x_A \overrightarrow{a} + y_A \overrightarrow{b}$, где $\overrightarrow{a}$ и $\overrightarrow{b}$ — векторы, порождающие решетку. Тогда $\overrightarrow{OA}_k = k(x_A \overrightarrow{a} + y_A \overrightarrow{b}) = (kx_A) \overrightarrow{a} + (ky_A) \overrightarrow{b}$.

Условие, что $A_k$ менее чем на $\varepsilon$ отстоит от узла решетки (рис. 7), будет выполнаться, если каждая из координат $(kx_A)$ и $(ky_A)$ будет отличаться от целого менее чем на $c.\varepsilon$, где $c$ — коэффициент, не зависит от $k$:

$$\text{можно, например, взять } c = \frac{1}{2\max(|\overrightarrow{a}|, |\overrightarrow{b}|)}$$

Действительно, пусть $\overrightarrow{OF} = \overrightarrow{ma} + \overrightarrow{nb}$.

Рис. 8.

Тогда, если

$$|m|\overrightarrow{a}| - kx_A|\overrightarrow{a}| \leq \frac{\varepsilon}{2} \text{ и } |n|\overrightarrow{b}| - ky_A|\overrightarrow{b}| < \frac{\varepsilon}{2}, \text{ то } |A_kF| = |A_hF| = |\overrightarrow{OF} - \overrightarrow{OA}_k| = |m\overrightarrow{a} + n\overrightarrow{b} - kx_A\overrightarrow{a} - ky_A\overrightarrow{b}| = |(m - kx_A)\overrightarrow{a}| + (n - ky_A)\overrightarrow{b}| \leq |(m - kx_A)\overrightarrow{a}| + |(n - ky_A)\overrightarrow{b}| + |m\overrightarrow{a}| - kx_A|\overrightarrow{a}| + |n|\overrightarrow{b}| - ky_A|\overrightarrow{b}| < \frac{\varepsilon}{2} + \frac{\varepsilon}{2} = \varepsilon.$$

Но неравенства $|m|\overrightarrow{a}| - kx_A|\overrightarrow{a}| < \frac{\varepsilon}{2}$ и $|n|\overrightarrow{b}| - ky_A|\overrightarrow{b}| < \frac{\varepsilon}{2}$ эквивалентны неравенствам $|m - kx_A| < \frac{\varepsilon}{2|a|}$ и $|n - ky_A| < \frac{\varepsilon}{2|b|}$. Поэтому если $kx_A$ и $ky_A$ отличются от целых менее чем на $\frac{\varepsilon}{2\max(|\overrightarrow{a}|, |\overrightarrow{b}|)}$, то $|A_hF| < \varepsilon$ для неокотогоюго узла $F$, а это и требовалось.

Нам нужно, чтобы вершины многоугольника $\Phi'$ попали в $\varepsilon$-окрестности узлов решетки. Так будет, если все числа $Nx_A, Ny_A, Nx_B, Ny_B$, … отличятся от целых менее чем на $c.\varepsilon$, что каждое из чисел $m\alpha_i$, где $i = 1, 2, ..., n$, отличается от целого менее чем на $\varepsilon$; то, что $\alpha$ было равно $\sqrt{3}$, не существует). Теорема Кронекара утверждает, что для набора $\alpha_1, \alpha_2, ..., \alpha_n$ любой длины при неокотогоюго натуральном $m$ числа $\alpha_i$ одно время не отличается от целых менее чем на $\varepsilon$.

Перейдем к доказательству теоремы Кронекара.

Рассмотрим $n$ последовательностей:

$$\{\alpha_1\}, \{2\alpha_1\}, \{3\alpha_1\}, ..., \{k\alpha_1\}, \dots$$

$$\{\alpha_2\}, \{2\alpha_2\}, \{3\alpha_2\}, ..., \{k\alpha_2\}, \dots$$

$$\{\alpha_n\}, \{2\alpha_n\}, \{3\alpha_n\}, ..., \{k\alpha_n\}, \dots$$

41

некоторые $k_1 < k_2 \leq M^n + 1$ наборы совпадут. В этом случае число $m = k_2 - k_1$ удовлетворяет условию, так как $\{m\alpha_i\} = \{(k_2 - k_1)\alpha_i\} = \{k_2\alpha_i - k_1\alpha_i\}$, а $\{k_1\alpha_i\}$ и $\{k_2\alpha_i\}$ находится в одном полупервале длины меньше $\varepsilon$, поэтому $m\alpha_i$ находится на расстоянии, меньше $\varepsilon$, от целого числа. Теорема доказана.

Do six pins pass matrizes reшетки на плоскости. Можно рассматривать и пространственные решетки. Они определяются так же, как плоские, только вместо двух неоклипных векторов нужно взять три некомпланных (рис. 9). Аналогично тому, как это делалось выше для многоугольников и плоских reшеток, определяется вписанность и почти вписанность многоугольников в пространственную reшетку. Какие из пяты правильных многоугольников (рис. 10) вписываются в целочисленную*) пространственную reшетку? Вот ответ:

Задача 4. Куб, тетраэдр и octаэдр вписываются в целочисленную reшетку.

Задача 5. Додекаэдр и икосаэдр не вписываются ни в какую reшетку.

Задача 6. Пусть в пространстве задано семейство параллельных плоскостей такое, что расстояния между соседними плоскостями семейства равны. Можно ли расположить в пространстве а) икосаэдр, б) додекаэдр так, чтобы их вершины лежали на плоскостях семейства?

Мы получили исчерпывающий ответ о вписывании правильных многоугольников в пространственную reшетку. Для почти вписывания тоже получается исчерпывающий ответ, такой же, как для плоского случая:

Задача 7. Любой многоугольник почти вписывается в любую reшетку в пространстве.

Все члены этих последовательностей принадлежат промежутку [0; 1[. Разобъем этот промежуток на кусочки (полупервалы) длины меньше $\varepsilon$:

$$\begin{align*} 0; \frac{1}{M} \mid ; \left[\frac{1}{M}; \frac{2}{M}\right] \mid \dots \mid \left[\frac{M-1}{M}; 1\right] \\ \mathrm{где} M - \mathrm{натуральное}, M > \frac{1}{\varepsilon} \quad (\mathrm{тогда} \frac{1}{M} < \varepsilon). \end{align*}$$

Теперь каждому из членов последовательностей поставим в соответствие тот кусочек промежутка [0; 1[, в котором он находится.

Тогда для каждого натурального $k$ будет определен упорядоченный набор полупервалов, соответствующих точкам $\{k\alpha_1\}$, $\{k\alpha_2\}, \dots, \{k\alpha_n\}$. Но так как рассматриваемых полупервалов всего $M$, а в каждый набор входит $n$ полупервалов, то число различных таких наборов равно $M^n$. Если $k$ пробегает значения от 1 до $M^n + 1$, то для