Задача M320

Условие

Какие выпуклы $n$-угольники можно разбить на треугольники так, чтобы никакие два из треугольников разбиения не имели общих (полностью совпадающих) сторон? (На рисунке 1 показано, что треугольник так разбит можно.)

А. Печковский

Решение

Какие выпуклы нуzelольники можно разбить на треугольники mak, чтобы никакие два из треугольников разбиения не имели общих (полностью совпадающих) стороны? (На рисунке 10 показано, что треугольник mak разбить можно).

Рис. 10.

Рис. 11.

Докажем, что при $n > 3$ n-угольник нельзя разбить на треугольники требуемым образом.

Предположим противное, — что мы все же разбили n-угольник ($n > 3$) на треугольники.

Оторазим множество сторон треугольников разбиения во множество их вершин. Будем при этом различать два случая.

1. Сторона треугольника разбиения не лежит на стороне n-угольника.

Тогда:
a) если сторо внутри этой стороны треугольника есть вершины других треугольников разбиения, то отображим ее в одну из таких вершин;
b) если же внутри этой стороны нет других вершин, то по определению разбиения один из концов этой стороны должен лежать сторо внутри некоторой другой стороны (другого треугольника разбиения), — отображим тогда нашу сторону именно в такой ее конец (если же она конца стороны лежат сторо внутри какой-то другой стороны, то отображим ее в любой из ее концов).
2. Сторона треугольника разбиения лежит на стороне n-угольника.

Оторазим такую сторону в тот ее конец, который встреется перым при обходе сторона n-угольника по часовой стрелке.

Рассмотрим теперь множество всех вершин треугольников разбиения. Все вершины делятся на три типа.

I тип. Вершины n-угольника и те вершины треугольников разбиения, которые лежат на сторонах n-угольника.

Пусть вершин I типа t. Тогда сторон, которые отображились в эти вершины, тоже t, так как оченьindo, что в такие вершины отображаются только стороны, лежащие на сторонах n-угольника, причем это отображение взаимно-однозначно.

II тип. Вершины, не лежащие на сторонах n-угольника и не лежащие сторо внутри сторон каких-либо треугольников разбиения (например, как на рисунке 11).

Пусть вершин II типа m. По построению в такие вершины не отображится ни одной стороны.

III тип. Вершины, не лежащие на сторонах n-угольника, но лежащие сторо внутри каких-то сторон треугольников разбиения (например, как на рисунке 12).

*) См. статью И. Н. Бронштейна «Эллипс», 1975, № 1.

Пусть вершин III типа $k$. В вершину III типа может отразиться не более трех сторон (сторона, внутри которого эта вершина лежит, и две стороны, для которых эта вершина служит коном — для одной левым, для другой — правым). Поэтому в $k$ вершин III типа может отразиться не более $3k$ сторона треугольников.

Пусть в разбиении $x$ треугольников. Выразим число $3x$ сторон треугольников через $t$, $k$ и $m$. Для этого запишем сумму углов этих треугольников.

С одной стороны, сумма углов $x$ треугольников равна $π(t-2)+2πm+πk$, где $π(t-2) = π(t-n)+π(n-2)$ — сумма углов при вершинах I типа, $2πm$ — сумма углов при вершинах II типа, $πk$ — сумма углов при вершинах III типа.

Следовательно,

$$πx = π(t-2) + 2πm + πk,$$

и общее число сторона равно

$$3x = 6m + 3t + 3k - 6.$$

Поскольку каждая из сторон треугольников разбивается в какую-либо вершину I или III типов, то из сказанного выше следует, что всего сторон может быть не более чем $t+3k$. Значит,

$$6m+3t+3k-6 \leq t+3k,$$

откуда $t+3m \leq 3$.

Но $t>0$ и $m>0$; кроме того, $t \geq n>3$, и мы получаем противоречие.

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

Кроме того, из последнего неравенства следует, что при разбении треугольника вершин II типа получится не может ($t=3$, следовательно, $m=0$).

А. Печковский