Целые точки в многоугольниках и многогранниках

13

Цельные точки в многоугольниках и многогранниких

В этой статье мы будем занимать многоугольники, все вершины которых лежат в целых точках координатной плоскости — в узлах клетчатой бумаги. Пусть $F$ — такой многоугольник, а $S(F)$ — его площадь. Если $N(F)$ — число узлов, попавших внутри и на гранису многоугольника $F$, то $S(F) \approx N(F)$. Для $S(F)$ есть и точные формулы, например, формула Пика («Квант», 1974, № 12):

$$S(F) = N(F) - B(F)/2 - 1,$$

где $B(F)$ — число узлов, попавших на гранису $F$.

Формула Пика обладает одним недостатком: она не имеет прямого анализа в пространстве. Приведенный на рисунке 1 пример показывает, что объем $V(F)$ многогранника $F$ с вершинами в узлах кубического решетки нельзя выразить через $N(F)$ — число узлов, попавших внутри и на гранису $F$, и через $B(F)$ — число узлов, попавших на гранису $F$. Можно, однако, придумать похожие формулы, которые прекрасно обобщаются на пространственный случай.

В этой статье будет построена небольшая теория, которая позволяет уладать и доказать все мыслиные аналоги формулы Пика на плоскости и в пространстве *).

*) См. задачу М385, «Квант», 1976, № 5.

§ 1. Введение

Сколько решений имеет система уравнений

$$\begin{cases} P(x, y) = 0, \\ Q(x, y) = 0, \end{cases}$$

где $P$ и $Q$ — многочлены от $x, y$ с действительными коэффициентами?

Что ответить на этот вопрос, для каждой однолетена $x^m y^n$, входящero с ненулевым коэффициентом хотя бы в один из многочленов $P$ или $Q$, отметим на координатной плоскости точку с координатами $(m; n)$. Возьмем выпуклу оболочку отмещенных точки — наименьший выпуклый многоугольник, содержащий все отмещенные точки. Этот многоугольник называется многоугольником Ньютона *) системы (1). Его удобно рисовать на клетчатой бумаге.

Решив пару десятков системы вида (1), я стал подозревать, что справедлива такая

Теорема 1. Число ненулевых решений системы (1) либо бесконечно, либо не превосходит удовеной площади ее многоугольника Ньютона.

Рис. 1. $N(T_n) = 4$, $B(T_n) = 4$, $V(T_n) = n/6$.

14

(Решение $(x_0, y_0)$ называется ненулевым, если $x_0 \neq 0$ и $y_0 \neq 0$.) Пытаясь доказать теорему 1, я почти доказал, что справедлива похожая на нее

Теорема 2. Число ненулевых решений системы (1) либо бесконечно, либо не преосходит $N(2F) - 2N(F) + 1$, где $2F$ — многоугольник, полученный из $F$ расстоянием в два раза относительно начала координат (рис. 2).

Чтобы окончить довольно длиное доказательство теоремы 2, мне оставалось показать, что

a) для любого целочисленного многоугольника $F$ функция $N(nF)$ — многочлен второй степени от $n$ при целых $n \geq 0$ (я называю многоугольник целочисленным, если его вершины лежат в узлах).

Пытаясь понять, какая из теорем — 1 или 2 — сильнее, я убедился что

b) для любого целочисленного многоугольника

$$2S(F) = N(2F) - 2N(F) + 1,$$

т. е. теоремы 1 и 2 по существу совпадают.

Оказывается, что и a) и b) в два счета выводятся из формулы Пика.

Уражение 1. Выведите a) и b) из формулы Пика.

Задание 1. Сформируйте аналог теоремы 1 для системы уравнения $P(x, y, z) = Q(x, y, z) = R(x, y, z) = 0$ и аналог формулы b) для многоугольников. Приуманную формулу проверьте, глаяя на рисунок 3.

$$2S(F) = N(2F) - 2N(F) + 1$$

§ 2.

Мы начнем построение обещанной выше теории с того, что честно доказем эту простую формулу. Обозначим ее правую часть через $P(F)$. Покажем, что если целочисленный многоугольник $F$ разбит диагональю $I$ на многоугольники $F_1$ и $F_2$, для которых формула 6) верна, то она верна и для $F$. Действительно, так как $N(F) = N(F_1) + N(F_2) - N(I)$, то и $P(F) = P(F_1) + P(F_2) - P(I)$. Очевидно, что $S(F) = S(F_1) + S(F_2)$. Поэтому $2S(F) = 2S(F_1) + 2S(F_2) = -P(F_1) + P(F_2) = P(F) + P(I)$. Легко проверить непосредственно, что для любого целочисленного отрезка $I$ (т. е. отрезка, концы которого — целые точки) $P(I) = 0$. Значит, $2S(F) = P(F)$. Таким образом, из справедливости 6) для треугольников по индекции вытекает справедливость 6) для $n$-угольников: целочисленный четырехугольник можно разрезать на два целочисленных треугольника, пятуюугольник — на четырехугольник и треугольник и т. д.

Формулу 6) легко проверить непосредственно для прямоугольников, составленных из целых клеток (рис. 4). Возьмем «половинку» такого прямоугольника $F$ — прямоугольный треугольник $F_1$. Мы уже знаем, что $2S(F) = P(F)$. По симметрию $S(F_1) = S(F_2) = S(F)/2$ и $P(F_1) = P(F_2)$. Так как $P(I) = 0$, то $P(F) = 2P(F_1)$, откуда $2S(F_1) = P(F_1)$. Таким образом, формула 6) доказана нами

Рис 3. $N(F) = (p+1)(q+1)(r+1)$,
$B(F) = N(F) - (p-1)(q-1)(r-1)$,
$V(F) = pqr$.

15

Рис. 4 $N(F) = (p+1)(q+1)$, $N(2F) = (2p+1)(2q+1)$, $S(F) = pq$.

для прямогольных треугольников (с катетами, параллельными осями).

Произвольный целочисленный треугольник можно получить, последовательно отрезая от подходящого прямогольника прямогольные треугольники (рис. 5). Значит, формула 6) верна для любого целочисленного треугольника, что и оставалось доказать.

§ 3. Как мы будем обобщать рассужения из § 2

Для того, чтобы доказать другие формулы, например, формулу Пика, мы могли бы повторять рассужения § 2 и доказывать совпадение двух функций, определяемых на множество всех целочисленных многоугольников. В § 2 таких функций были 2S(F) и P(F) для доказательства формулы Пика мы взяли бы S(F) и N(F)—B(F)/2—1 и т. д. Такой подход плох по трем принимам. Во-первых — это очень скучно. Во-вторых — так можно доказывать уже угаданные формулы, но нельзя придумать новые. В третьих — действия таким образом, мы никогда не будем увеличены в том, что получили все интересные формулы.

В двух аксиоматического подхода, выработанного математкой XX века, мы постараемся сразу описать весь класс функций, к которым применены рассужения § 2. Для этого нужно хорошо проанализировать решение задачи 6). Стандартная схема такого анализа в нашем случае выглятит так:

Шаг 1. Нужно перечислить те свойства функций, определяемых на множество целочисленных многоугольников, которые используются при решении исходной задачи.

Шаг 2. Нужно изучить все функции, обладающие этим свойствами. (Мы назовем их удобными.)

Шаг 3. Нужно доказать критерий совпадения функций и описать все удобные функции. (Критерий должны быть простым, и его применение должно сразу решать исходную задачу.)

Шаг 4. Нужно применить полученный критерий для обобщения исходной задачи.

§ 4. Замечательные функции на множество плоских целочисленных функур

Одиним многоугольниками не обойтись

Читатель, верятоно, уже заметил, что в рассужениях § 2 встречались не только многоугольники, но и отрезки.

Оределение. Плоской целочисленной функции (или просто функций) мы будем назвать целую точку, целочисленный отрезок или целочисленный многоугольник. Множество всех плоских целочисленных функур обозначает Ф.

Мы будем рассматривать обрабатываемая Ф в множестве действительных чисел — функции на множестве Ф.

16

Рис. 6. «Перекос». $T(x, y) = (x+y; y);$
$T(1; 3) = (4; 3)$.
Каждая горизонтальная прямая $\{(x; y)|y=c\}$ под действием «перекоса» $T$ сдигается сма по себе на расстояние $c$. Каждая вертикальная прямая «перекашивается» подобно оси $y$, которая переходит в пунктарную прямую.

Шаг 1 — какие функции на Ф мы будем рассматривать.

Функцию $f$ на множество $\Phi$ будем называть addимивной, если она обладает следующим свойствам:

A) если целочисленные функции $F, F_1, F_2$ максимы, что $F = F_1 \cup F_2$, а $F_1 \cap F_2$ — мощка или отрезок, мо
$f(F) = f(F_1) + f(F_2) - f(F_1 \cap F_2)$.

Введем на плоскости координаты $x, y$. Допустимыми будем называть преобразования четырех типов:

1°. параллельные переносы на целочисленный вектор $(a; b)$: $T(x; y) = (x+a; y+b)$;
2°. симметрины: $T(x; y) = (\pm x; \pm y)$;
3°. перестановку координат: $T(x; y) = (y; x)$;
4°. «перекосы»: $T(x; y) = (x+ay; y)$, где $a$ — произвольное целое число (рис. 6).

Функция $f$ на множество $\Phi$ называется инвариантной относительной преобразования $T$, если для любой функции $F \in \Phi$ выполено равенство $f(TF) = f(F)$.

Функцию $f$ будем называть инвариантной, если она инвариантна относительно любого допустимого преобразования.

У разженние 2. Докажите, что функция $R$, принимающая на любой целой точке значение 0, на любом целочисленном отрезке значение 2, а на любом целочисленном $n$-угольнике — значение $n$, инвариантна, но не адитивна.

Основное определение. Функцию $f$ на множество $\Phi$ будем называть addимивной, если она адитивна и инвариантна.

Примеры удобных функций

Множество всех удобных функций на $\Phi$ мы обозначим через $Y$. Удобные функции существуют. Например, функция $E$, сопоставляющая каждой целочисленной функре число 1, является удобной. Очевидно, что функция $N$, сопоставляющая каждой целочисленной функре $F$ число $N(F)$, является удобной. Ясно, что функция $S$ — адитивна. Очевидно также, что $S(TF) = S(F)$ для любой функции $F$ и для любого допустимого преобразования $T$ типов $1^\circ - 3^\circ$. Интуитивно очевидная инвариантность функции $S$ относительно «перекосов» следует из принципа Кавальери (см. «Алгебра и начала анализа 10», п. 107). Значит, функция $S$ — удобная. Из уже известных удобных функций можно получить новые по следующему правилу.

У разженние 3. Для любой функции $F \in \Phi$ обозначим через $nF$ функру, полученную из $F$ растяжением в $n$ раз относительно начала координат. Докажите, что если $f \in Y$, то функция $f_n$, сопоставляющая каждой функре $F$ число $n(F)$, также является удобной.

В частности, функция $N_n$, сопоставляющая функре $F$ число $n(F)$, является удобной.

Задание 2. Докажите, что всякая удобная функция $f$ обладает следующим свойствам:

B) $f$ принимает одинаковое значение на всех целочисленных отрезках $I$ максим, что $N(I) = 2$.

Заметим, что выбор аксиом, описывающих множество удобных функций, является в значительной степени произвольным. Мы предложили такой набор аксиом, который легче всего обобщается на трехмерный случай; но можно было бы обойтись и меншшим числом аксиом. Вот пример.

Задание 3. Обозначим через $Y'$ множество адитивных функций, инвариантных относительно преобразования типа $1^\circ - 2^\circ$ и.addимых свойствам B). Докажите, что $Y' = Y$.

Эту задачу стоит решать после того, как будут найдены все удобные функции.

18

Рис 8. $F = F_1 \cup F_2$.

Еще один пример удобной функции
Можно ли применить основную теорему для доказательства формулы Пика? Беда в том, что функция $B$ определяна пока лишь на множество настоя щи и х целочисленных многоугольников. Как определять ее на отрезках и точках? Если мы хотим продолжить $B$ до удобной функции на Ф, то из рисунка 8 видно, что нам следует положить $B(I) = B(F_1) + B(F_2) - B(F)$, и из этого же рисунка ясно, что права часть этого равенства есть $2 + 2 \cdot (\text{число неконечных мочек отрезка } I)$. Наконец, если $X$ — точка, то по тем же причине нам следует положить $B(X) = 0$.

У права не ие 4 (устное). Докажите, что определяющая выше функция $B$ действительно является удобной.

Докажем теперь формулу Пика. Из определения функции $B$ вытекает, что вопросительный знак в шестой строке таблицы 1 можно заменить на $B$. Но выше мы выяснили, что эта строка соответствует функции $2N$ — $2E$—$2S$. Значит, по основной теореме, $N$—$E$—$B/2 = S$.

Вопрос — предстержение. Почему из равенства $\vec{R} = \vec{B}$, где $R$ — функция из управления 2, не вытекает, что $R = B$?

Шаг 4 — обобщаем формулу 6) и формулу Пика.

Пусть $e, f, g, h$ — четыре удобные функции, $e, f, g, h$ — соответствующее им четыре вектора в пространстве. Однако из них всегда можно представить как сумму трех других с действительными коэффициентами. По основной теореме то же верно и для исходных функций. Выбирая в качестве $e, f, g, h$ различные удобные функции (определенные чисто геометрические), мы будем получить новые геометрические формулы. Выразим, например, $B(F)$ через $N(F)$ и $N(2F)$. Возьмем четыре удобные функции $B, E, N, N_2$. Будем искать числа $c_1, c_2, c_3, c_4$ также, что $B = c_1E + c_2N + c_3N_2$. Эта задача свидетелься к решению следующей системы управления (см. таблицу 1):

$$\begin{cases} 0 = c_1 + c_2 + c_3, \\ 2 = c_1 + 2c_2 + 3c_3, \\ 3 = c_1 + 3c_2 + 6c_3. \end{cases}$$

Решая ее, получим $c_1 = -3, c_2 = 4, c_3 = -1$, т. е. $\vec{B} = 4\vec{N} - \vec{N}_2 - 3\vec{E}$. Значит, для любого целочисленного многоугольника $F$

$B(F) = 4N(F) - N(2F) - 3$.

У права не ие 4 (устное). Докажите, что определенная выше функция $B$ действительно является удобной.

§ 5. Замечательные функции на множество пространственных целочисленных функур

Целочисленной функцией (или просто фигурой) в трехмерном пространстве мы назовем целочисленную функцию, целочисленную отрезок, целочисленный многоугольник или целочисленный многоугольник. Множества целочисленных функур обозначим, как в двумерном случае, через $\Phi$.

Строое определение удобной функции на множество $\Phi$ мы даим в «Приложении». Сейчас для нас будет важно то, что функция $E, N, N_n, V$ оказывается удобным. Пусть $A_1, A_2, A_3, A_4$ — точки трехмерного пространства с координатами $(0; 0; 0), (1; 0; 0), (0; 1; 0), (0; 0; 1)$. Пусть $X_1$ — точка $A_1, X_2$ — отрезок $A_1A_2, X_3$ — треугольник $A_1A_2A_3, X_4$ — тетрадр $A_1A_2A_3A_4$.

Каждай удобной функции $f$ сопоставим четырьмя чисел — ее значения на функрах $X_1, X_2, X_3, X_4$. Какие четырьмя получаются для известных нам функций $V, E, N, N_2, N_3$ показано в строках 1—5 таблицы 2.

Предположим еще, что для удобных функций на множество $\Phi$ справедливо обозначение основной теоремы из § 4:

Если $h$ — удобная функция на Ф, и $h(X_1) = h(X_2) = h(X_3) = h(X_4) = 0$, то функция $h$ есть точдействий нулы.

19

§ 6. Приложение

Доказательство основной теоремы.

Если $X$ — целая точка, то параллельным пересечением ее можно перевести в точку $X_1$. Поэтому $h(X) = h(X_1) = 0$.

Если $I$ — целочисленный отрезок и $N(I) = 2$, то согласно решению задачи 2 $h(I) = h(X_1) = 0$.

Если $N(I) > 2$, то разобем отрезок $I$ точкой $X$ на два отрезка $I_1$ и $I_2$ такие, что $N(I_1) < N(I)$, $N(I_2) < N(I)$. Согласно А), $h(I) = h(I_1) + h(I_2) - h(X) = h(I_1) + h(I_2)$. Приемняя индикцию, получаем, что $h(I) = 0$ для любого целочисленного треугольника $F$. Из свойства А) и рисунка 5 следует, что это равенство будет справедливо, если $h$ обращается в нуль на всех прямогольников со стороны, параллельными осем координат, параллельными осем координат.

Оказывается, если $h$ обращается в нуль на прямогольник со стороны, параллельными осем координат, параллельными осем координат, то $h$ обращается в нуль на прямогольник треугольника $F$. Из свойства А) и рисунка 5 следует, что это равенство будет справедливо, если $h$ обращается в нуль на всех прямогольников со стороны, параллельными осем координат, параллельными осем координат.

Оказывается, если $h$ обращается в нуль на прямогольник со стороны, параллельными осем координат, параллельными осем координат, то $h$ обращается в нуль на прямогольник треугольника $F$. Из свойства А) и рисунка 5 следует, что это равенство будет справедливо, если $h$ обращается в нуль на всех прямогольников со стороны, параллельными осем координат, параллельными осем координат.

Оказывается, если $h$ обращается в нуль на прямогольник со стороны, параллельными осем координат, параллельными осем координат, то $h$ обращается в нуль на прямогольник треугольника $F$. Из свойства А) и рисунка 5 следует, что это равенство будет справедливо, если $h$ обращается в нуль на всех прямогольников со стороны, параллельными осем координат, параллельными осем координат.

Пусть теперь $F$ — произвольный целочисленный многоугольник. Разбивая $F$ диагональю $I$ на два многоугольника $F_1$ и $F_2$ с меньшим, чем $y$, числом сторон, мы получаем, согласно А), что $h(F) = h(F_1) + h(F_2) - h(I) = h(F_1) + h(F_2)$. Приемняя индикцию, получаем, что достаточно доказать равенство $h(F) = 0$ для любого целочисленного треугольника $F$. Из свойства А) и рисунка 5 следует, что это равенство будет справедливо, если $h$ обращается в нуль на всех прямогольников со стороны, параллельными осем координат, параллельными осем координат.

Действительно, разобем такой прямогольник $F$ диагональю $I$ на треугольники $F_1$ и $F_2$. Тогда $h(F) = h(F_1) + h(F_2)$. Предположим, что $h(F) = 0$, тогда $h(F_1) + h(F_2) = 0$. Доказем, что $h(F_1) = h(F_2)$. Пусть $F'_1$ — треугольник, симметричный $F_1$ относительно одной из координатных осей, а $F'_2$ — треугольник, симметричный $F_2$ относительно другой координатной оси. Поскольку $h$ инварианта относительно симметричной получаем $h(F_1) = h(F_1')$, $h(F_2) = h(F_2')$. Но $F'_1$ можно перевести в $F'_2$ па-

Рис. 9.

20

Рис. 10.

раплельным переносом, поэтому $h(F_1') = h(F_2')$. Отсюда $h(F_1) = h(F_2)$ и, значит, $h(F_1) = h(F_2) = 0$.

Осталось показать, что $h$ обращается в нуль на прямогольниках со стороны, параллельными координатным осям. Разбивая такой прямогольник на меньше прямогольники, мы получаем по индукции, что достаточно доказать обращение $h$ в нуль на единичном квадрате $X_3 \cup Y_3$, изображенном на рисунке 10. Согласно А), $h(X_3 \cup Y_3) = h(X_3) + h(Y_3)$. По условию теоремы $h(X_3) = 0$. Выше мы доказали, что $h(Y_3) = h(X_3)$, поэтому и $h(Y_3) = 0$. Отсюда $h(X_3 \cup Y_3) = 0 + 0 = 0$. Доказательство теоремы законено.

Решение задачи 2.

Будем говорить, что функция $F_1$ и $F_2$ эквивалентны (обозначается: $F_1 \sim F_2$), если функция $F_1$ получается из функций $F_2$ целочкой допустимых преобразований. Ясно, что всякая удобная функция принимает одинаковое значение на эквивалентных функрах. Обозначим через $I_a,b$ отрезок с концами $(0; 0)$ и $(a; b)$. Покаем, что всякий отрезок $I_a,b$ эквивалентен отрезку $I_{n,0}$. Преобразование $1^\circ$ любой отрезок $I$ переводится в $I_a,b$. Сделав преобразования $2^\circ$ и $3^\circ$, можно считать, что $a \geq b \geq 0$. Если $b > 0$, то рассмотрим все отрезки, которые можно получить из $I_a,b$ с помощью «перекосов». Из рисунка 11 видно, что среди таких отрезков обязательно есть отрезок $I_c,b$, где $0 \leq c < b$. Сделав $3^\circ$, получаем, что $I_a,b \sim I_b,c$. Повторив несколько раз те же расхождения, мы получим, что $I \sim I_{n,0}$. Если дополнительно известно, что $N(I) = 2$, то $N(I_{n,0}) = 2$, т. е. $n = 1$. Таким образом, удобная функция $f$ на любом отрезке $I$, для которого $N(I) = 2$, принимает такое значение, как и отрезке $I_{1,0}$.

Определение удобных функций на Ф в пространственном случае.

Адитивность. Функция $f$ на множество $\Phi$ называется $\Phi$ на функция $F \in \Phi$ на функцию $F_1$, …, $F_k \in \Phi$, удовлетворяющего условиям $F_1 \cap F_2 \cap \dots \cap F_k \neq \emptyset$ и $V(F_i \cap F_j) = 0$ при $i \neq j$, выполено ра-