Вокруг формулы Пика

39

Чтобы оценить площадь многоугольника, нарисованного на клетчатой бумаге, достаточно подсчитать, сколько клеток покрывают этот многоугольник (плошадь клетки мы принимаем за единицу). Точнее, если $S$ — площадь многоугольника, $N_1$ — число клеток, которые целиком лежат внутри многоугольника, и $N_2$ — число клеток, которые имеют с внутренностью многоугольника хотя одну общую точку, то $N_1 \leqslant S \leqslant N_2$. (Этот факт можно использовать для того, чтобы дать точное определение площади многоугольника и других функций.)

Мы будем рассматривать ниже только такие многоугольники, все вершины которых лежат в узлах клетчатой бумаги — в точках, где пересекаются линни сетки. Оказывается, что для таких многоугольников можно указать простую формулу:

$$S = \frac{r}{2} + i - 1,$$

где $S$ — площадь, $r$ — число узлов, которые лежат на границе многоугольника (то есть на сторонах и в вершинах), $i$ — число узлов, которые лежат строго внутри многоугольника.

Эту формулу называют иногда «формулой Пика» — по имени математика, открывшего ее в 1899 году. (Впрочем, нельзя уверенным в том, что эту естественную формулу, допускающую целый ряд различных доказательств, не придумал никто ранее.)

40

ke 1, вы убедитесь, что площадь получается всегда равной «получению» числу — числу вида $m/2$, где $m$ — целое.

Назовем треугольник простым, если ни внутри него, ни на его сторонах нет узлов сетки, за исключением вершин. (Такое название выбранно потому, что любой другой треугольник можно составить из простых; это одно из тех утверждений, которые попадаются нам ниже.) Обратите внимание, что все простые треугольники на рисунке 1 имеют площадь 1/2. Мы увидим, что это не случайно.

В решении задачи M226, опубликованной в «Кванте», 1974, № 6, читателем предлагалось подумать над такой задачей. Три кузнечки (при мочи) в начальной момент времени седят в трех вершинах одной клетки, а затем нацинают «церambь в чехарду»: каждый может прыщнуть через однозоно из двух других, после чего оказывается в симметричной относительной нео точеке (рис. 2; ясно, что после любого числа пыжков кузнечки будут попадать в узлы клетки). В каких проекках может через несколько пыжков оказаться кузнечки?

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

Теорема 1. Следующие три свойства треугольников с вершинами в узлах клетчатой бумаги эквивалентны друг друга:

1. треугольник имеет площадь 1/2;
2. треугольник прост;
3. треугольник дистрижим.

В справедливости этой теоремы вы можете убедиться, доказав следующее теорему отмечены те, к доказательству которых имеется указания в конце курпала. Остальные—почти оченьды, если доказывать их в таком порядке:

$$3 \Rightarrow 4 \quad 1 \Rightarrow 2 \quad 10$$

$$5 \Rightarrow 6 \Rightarrow 7 \Rightarrow 8 \Rightarrow 9 \Rightarrow 11 \Rightarrow 12$$

1. Площадь треугольника при прыжке не меняется.
2. Любой доступный треугольник имеет площадь 1/2.
   3 *. Если достроить простой треугольник $ABC$ до параллелограмма $ABCD$, то ни внутри, ни на сторонах этого параллелограмма не будет узлов (не считая вершин).
   4 *. Из простого треугольника при прыжке получается простой.
   5 *. У простого треугольника один из углов — тупой или прямой (причем последний случай возможен только для треугольника, у которого три вершины принадлежат одной клетке; такой простой треугольник — со стороными 1, 1, $\sqrt{2}$ мы будем назвать минимальным).
3. Из любого простого не минимального треугольника можно одним прыжком получить треугольник, у которого наиболее стороны меньше, чем наиболее стороны стороны исходного.
   7 *. Любой простой треугольник можно конечным числом прыжков перевести в минимальный.
4. Любой простой треугольник доступим.
5. Любой простой треугольник имеет площадь 1/2.
   10 *. Любой треугольник можно разрезать на простые.
6. Площадь любого треугольника равна $m/2$, причем при любом разрезании его на простые их количество равно $m$.

41

12. Любой треугольник площади 1/2 — простой.
    Ясно, что из утверждений 2, 8 и 12 вытекает теорема 1.
    Докажите еще несколько свойств треугольников.
13. Для любых двух узлов A и B решетки, на отрезке между которых нет других узлов, найдется узел C такой, что треугольник ABC — простой.
14. Узел C в предыдушей задаче можно всегда выбрать так, что угол ACB будет тупым или прямым.
15. Параллелограмм тогда и только тогда порождаем решетку, состояшую из всех узлов клетчатой бумаги (см. статю А. А. Егорова, с. 26), когда каждый из треугольников, на которые его делит диагональ, — простой.
    To же самое свойство можно сформировать так.
16. Треугольник ABC — простой тогда и только тогда, когда всевозможные треугольники, полученные из ABC параллельными переносами, переводящими узел A в различных узлы решетки, не накладываются друг на друга (рис. 3).

Вернемся теперь к задаче про трех кузнечников. Пусть кузнечники в начальном положении занимают какой-то определенный (а не произвольный) минимальный треугольник — в первоначальной формулировке задачи именно это и предполагаюсь. Поскольку каждый кузнечик смешается при прыжке обязательно на четное число клеток по горизонтали и вертикали, то он обязательно попадает в узел «с во ей» решетки с размером клеток 2×2. На рисунке 4 три из четырех «подрешеток», составляющих всю решетку, раскрашены в разные цветы (кажый кузнечик прыгает в узлы своего

Цвета), а четвертая — того же цвета, что и линия сетки.

Согласно теореме 1 кузнечники могут одновременно попасть в вершины простого треугольника.

Отсюда вытекает еще одно интересное свойство этих треугольников.

17. Если решетку — узлы клетчатой бумаги — разбит на четыре подрешетки с клетками 2×2 (рис. 4), то вершины простого треугольника обязательно попадут в три разны e подрешетки (все три имеют разный цвет).

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

18. Три кузнечника могут одновременно попасть в те и только те трейки точек, которые служат вершинами простого треугольника и имеют тот же цвет, что и соответствующие вершины начального треугольника.

19. Два кузнечника могут одновременно попасть в те и только те узлов соответствующих цветов, на отрезке между которых нет других узлов.

Триангуляция многоугольника
Мы подробно изучили частный вид многоугольников на клетчатой бумаге, которое в формуле Пика соответствует значения i = 0, r = 3, S = 1/2. Но от этого частного случая можно перейти сразу к самому общему, воспользовавшись теоремой о разрешении на треугольника произвольного многоугольника (клетчатая бумага больше не нужна).

42

Рис. 5.

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

Теорема 2. a) Любой $n$-угольник можно разрезать диагоналими на треугольники, причем количество треугольников будет равно $n-2$.
(Это разбиение—триангуляция с вершинами в вершинах $n$-угольника.)

6. Пусть на границе многоугольника отмещено $r$ точек (включая все вершины), внутри — еще $i$ точек. Тогда существует триангуляция с вершинами в отмещенных точках, причем количество треугольников максимimalmente будет равно $r+2i-2$.

Разумеется, a) — частный случай, 6), когда $r=n$, $i=0$. Доказательство этой теоремы мы снова разобем на ряд простых утверждений.

20 *. Из вершины наиболее угла $n$-угольника ($n>3$) всегда можно проведить диагональ, целиком лежащую внутри многоугольника.

21. Если $n$-угольник разрезан диагонально на $p$-угольник и $q$-угольник, то $n=p+q-2$.

22. Любой $n$-угольник можно разрезать диагоналями на $n-2$ треугольника.

23. Сумма углов $n$-угольника равна $180^\circ \cdot (n-2)$.

24. Для любого треугольника, внутри и на границе которого отмещено несколько точек (в том числе — все три его вершины), существует триангляция с вершинами в отмещенных точек.

25. To же самое верно и для любого $n$-угольника.

26. Число треугольников триангляции равно $r+2i-2$, где $i$ и $r$ — количество отмещенных точек соответствующего внутри и на границе многоугольника.

Отсюда вытекает теорема 2.

27. Выведите из теорем 1 и 2 формулу Пика: $S=r/2+i-1$.

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

Назовем разбиение $n$-угольника на несколько многоугольников правильным, если каждая вершина одного из многоугольников разбиения служит вершиной всех других многоугольников разбиения, который она принадлежит.

28. Если из вершин $k$-угольников, на которых разбит правильным образом $n$-угольник.

43

Рис. 7

ник, $i$ вершин лежат внутри и $r$ — на границе $n$-угольника, то количество $k$-угольников равно

$$m = \frac{r + 2i - 2}{k - 2}.$$

29 (Вариант «теоремы Эйлера»). Если $N_0$ точек плоскости и $N_1$ отрезков с концами в этих точках образуют многоугольник, правильно разбитый на $N_2$ многоугольников, то (рис. 6) $N_2 - N_1 + N_0 = 1$.

Несколько задач

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

30. Пусть отношение площади многоугольника к квадрату одной из его сторон irrationalно (так объект дело, например, для правильного треугольника). Докажите, что подобный ему многоугольник нельзя на клетчатой бумаге так, чтобы вершины лежали в узлах.

31. Пусть $A$ и $B$ — два узла клетчатой бумаги, из которых второй на $p$ клеток правее и на $q$ — выше первого (то есть расстояние между узлами равно $\sqrt{p^2 + q^2}$). Чему равно расстояние до прямой $AB$ от ближайшего к ней узла, не лежшего на этой прямой?

32. Шахматный король обошел доску $8 \times 8$ клеток, побивав на каждом полеровно один раз и последним ходом вернулись на исходное поле. Ломаная, соединяющая последовательную центры полей, которые проходил король, не имеет самопересечений.

Рис. 8.

a) Какую наибольшую длину она может иметь?

6. Какую площадь может ограничивать эта ломанная? (Сторона клетки равна 1.)

Задача a) уже разбиралась в «Кванте» № 5 за этот год (с. 52) — она имеет номер M220 в «Задачике« «Кванта». Здесь мы приведем другое решение. Но начнем с задачи 6). Из формулы Пика сразу следует, что площадь, ограниченная ломаной, равна $64/2 - 1 = 31$ (узлами клетчатой бумаги служежат центры 64 полей; по условию все они лежат на границе многоугольника). Перейдем к задаче a). На рисунке 7 приведен пример пути короля, в котором 36 из 64 ходов имеют длину $\sqrt{2}$ (направлены по диагонали). Докажем, что больше 36 таких ходов быть не может.

На каждом отрезке длины $\sqrt{2}$, входящем в путь короля, постройм, как на диагонали, квадрат $1 \times 1$. Однако положка этого квадрата лежит вне многоугольника, который ограничивает путь короля. Но общая площадь, занятая такимими положками, не превышает 49—31=18, поскольку все они выходит за пределы квадрата $7 \times 7$ клетчатой бумаги. Значит, количество диагональных ходов не превышает 36.

Итак, ответы к задаче 32:

a) $28 + 36\sqrt{2}$; 6) 31.

33. Нужно проверить по линяям сетки замкнутую несамопересекающийся ломаную, которая бы проходила через все узлы клетчатой бумаги, лежащие внутри прямой прямой $p \times q$ клеток.

a) При каких $p$ и $q$ это возможно?

b) Какую длину будет иметь эта ломанная?

b) Какую площадь она будет ограничивать? (рис. 8).