Эта заметка посвящена решению задачи М1170. Напомним её условие:
Рассмотрим разбиения данного выпуклого $n$-угольника на треугольники непересекающимися диагоналями. Назовём перестройкой следующее преобразование: вместо некоторой диагонали $BC$, служащей общей стороной двух треугольников $ABC$ и $BCD$ разбиения, проводится диагональ $AD$ (рис. 1). Обозначим через $P(n)$ наименьшее число перестроек, за которое можно любое разбиение перевести в любое другое. Докажите оценки:
Рисунок номер 1
а) $P(n)\ge n-3$;
б) $P(n)\le2n-7$;
в)* $P(n)\le2n-10$ при $n\ge13$.
Эта задача была предложена в 1988 году на осеннем туре Турнира городов. А её источником явилось вышедшее в 1986 году весьма серьёзное исследование трёх известных американских математиков: Дэниэла Слейтора, Роберта Тарьяна и Уильяма Тёрстона. Они сумели найти гораздо более точные оценки снизу для числа $P(n)$, причём их метод доказательства настолько неожидан и изящен, что мы решили познакомить с ним читателей «Кванта».
Решение задачи М1170
Прежде всего дадим следующее определение: разбиение $n$-угольника называется коническим с вершиной $A$, если все образующие его диагонали выходят из одной точки — вершины $A$ $n$-угольника.
Теперь рассмотрим два конических разбиения — одно с вершиной $A$, а другое — с вершиной $B$, соседней с $A$. Эти два разбиения не имеют ни одной общей диагонали, и поэтому получить одно из другого менее чем за $n-3$ перестройки невозможно. В самом деле, при каждой перестройке множество диагоналей данного разбиения изменяется лишь на один элемент, а всего диагоналей в каждом разбиении $n-3$. Таким образом, мы доказали неравенство а): $P(n)\ge n-3$.
Докажем теперь, что не более чем за $n-3$ перестроек можно из любого разбиения получить коническое разбиение с произвольной заранее выбранной вершиной $A$. Для этого достаточно указать цепочку перестроек, каждая из которых добавляет новую диагональ, выходящую из вершины $A$.
Рассмотрим все треугольники разбиения с вершиной $A$. Допустим, что среди них есть треугольник $ABC$, сторона $BC$ которого является диагональю (а не стороной) нашего $n$-угольника. Тогда к этой диагонали примыкает ещё один треугольник разбиения $BCD$ (рис. 2). Заменим диагональ $BC$ на $AD$. Повторяя аналогичные перестройки, мы добьёмся того, что у всех треугольников разбиения с вершиной $A$ противоположная ей сторона будет одной из сторон $n$-угольника. А такое разбиение, очевидно, коническое.
Рисунок номер 2
Мы доказали даже более сильный факт: количество перестроек, необходимых для того, чтобы получить из данного разбиения коническое разбиение с вершиной $A$, не превосходит $n-3-x$, где $x$ — число диагоналей данного разбиения, выходящих из вершины $A$. Если выбрать вершину $A$ так, чтобы из неё выходила по крайней мере одна диагональ исходного разбиения, то нам потребуется не более чем $n-4$ перестроек для того, чтобы получить из него коническое разбиение с вершиной $A$, и не более чем $n-3$ перестроек, чтобы получить из этого конического разбиения второе разбиение. Тем самым доказано неравенство б): $P(n)\le (n-4)+(n-3)=2n-7$.
Теперь, чтобы доказать последнее неравенство в) $P(n)\le 2n-10=(n-3)+(n-3)-4$ при $n\ge13$, нам достаточно для любых двух разбиений найти такую вершину $A$, что суммарное количество выходящих из неё диагоналей первого и второго разбиений не меньше 4. Подсчитаем среднее число диагоналей произвольного разбиения, выходящих из одной вершины. Всего диагоналей $n-3$, каждая из них соединяет две вершины, а вершин всего $n$. Следовательно, в среднем на вершину приходится $\dfrac{2(n-3)}{n}$ диагоналей. Поэтому среднее суммарное число диагоналей первого и второго разбиений, выходящих из одной вершины, равно $\dfrac{4(n-3)}{n}$. При $n\ge13$ это число больше трёх и, значит, нужная нам вершина $n$-угольника действительно существует.
Триангуляция сферы и шара
Прежде чем приступить к изложению результатов Слейтора, Тарьяна и Тёрстона, необходимо дать несколько определений.
Триангуляцией сферы будем называть разбиение сферы на несколько областей, получаемое следующим образом: на сфере отмечается несколько точек — они называются вершинами триангуляции — и некоторые из них соединяются несамопересекающимися кривыми, которые могут пересекаться друг с другом только в вершинах. При этом каждая из областей, на которые разбивается сфера, должна иметь ровно три стороны, т. е. её должны ограничивать ровно три кривых.
Таким образом, при триангуляции сфера разбивается на несколько криволинейных треугольников. Пример показан на рисунке 3.
Рисунок номер 3
Специальной триангуляцией шара будем называть такое разбиение шара на несколько «криволинейных» тетраэдров, что все их вершины лежат на сфере, ограничивающей шар.
Не удивляйтесь, если далее мы иногда будем словом «шар» называть нечто, совсем на шар не похожее, например, куб. Дело в том, что куб можно, немного помяв, превратить в шар. При этом, конечно, триангуляция куба перейдёт в триангуляцию шара и т. д.
Чрезвычайно удачная идея позволяет свести проблему более точного вычисления $P(n)$ к геометрической задаче. Надо «всего лишь» заметить, что переход от картинки, изображённой на рисунке 4, а, к картинке на рисунке 4, б очень похож на приклеивание тетраэдра (особенно, если пунктиром изобразить только что стёртую диагональ). Мы начинаем с исходной картинки — разбиения многоугольника — и «приклеиваем» к ней криволинейные тетраэдры (удобно представлять их себе почти плоскими). Вот как выглядит такое приклеивание, если мы превращаем разбиение $P$ в разбиение $Q$ (рис. 5).
Рисунок номер 4
Рисунок номер 5
Ясно, что вид сверху на полученную фигуру совпадает с разбиением $Q$. Если у двух разбиений $P$ и $Q$ нет общих диагоналей, то приклеив все криволинейные тетраэдры в соответствии с последовательностью перестроек, переводящих $P$ в $Q$, мы получим тело $B$, которое можно считать шаром. Его граничная поверхность — это «помятая» сфера $S$, экватор которой совпадает с нашим многоугольником, одна половина (нижняя) разбита диагоналями в соответствии с разбиением $P$, а другая (верхняя) — в соответствии с разбиением $Q$. Таким образом, для всякой триангуляции $t$ сферы $S$, получающейся склейкой двух разбиений $n$-угольника (не имеющих общих диагоналей), существует специальная триангуляция шара $B$ из $m$ тетраэдров, где $m\le P(n)$, такая, что рёбра тетраэдров, лежащие на сфере $S$, дают на ней триангуляцию $t$.
На рисунке 6, а приведён пример превращения одного разбиения шестиугольника в другое, а на рисунке 6, б — соответствующая специальная триангуляция шара (имеющего здесь вид октаэдра). Её составляют, в порядке приклеивания, следующие тетраэдры: 2436, 4536, 1236, 1536.
Рисунок номер 6
Однако не всякая триангуляция сферы может быть получена склеиванием двух разбиений $n$-угольника. Дело в том, что триангуляция сферы, которая получается такой склейкой, обладает дополнительным свойством: она имеет гамильтонов обход. Это означает, что есть замкнутый путь по кривым триангуляции, проходящий через каждую вершину ровно один раз. Поэтому далее мы будем рассматривать лишь триангуляции сферы, обладающие этим свойством (назовём их гамильтоновыми).
Лемма 1. Обозначим через $T(n)$ минимальное число «криволинейных» тетраэдров, из которых заведомо можно составить специальную триангуляцию шара $B$, дающую на сфере $S$ произвольную данную гамильтонову триангуляцию с $n$ вершинами. Тогда $P(n)\ge T(n)$.
Для доказательства рассмотрим два разбиения $P$ и $Q$ такие, что для перехода от $P$ к $Q$ требуется ровно $P(n)$ перестроек. Если эти разбиения не имеют общих диагоналей, то неравенство $P(n)\ge T(n)$ следует из рассуждения, изложенного выше. Остаётся показать, что разбиения $P$ и $Q$ не могут иметь общих диагоналей. Допустим, что это не так, и $AB$ — их общая диагональ, к которой в разбиении $P$ примыкают треугольники $ABC$ и $ABD$. Заменив $AB$ на $CD$, мы получим из разбиения $P$ новое разбиение $P'$. Как следует из двух приводимых далее комбинаторных лемм, для превращения $P'$ в $Q$ требуется не менее чем $P(n)+1$ перестроек. А это противоречит определению числа $P(n)$.
Лемма 2. Если перестройка $\alpha$ увеличивает число общих диагоналей у разбиений $P'$ и $Q$, то существует простейшая последовательность перестроек, превращающая $P'$ в $Q$ и начинающаяся с перестройки $\alpha$.
Лемма 3. Если разбиения $P$ и $Q$ имеют общую диагональ, то кратчайшая последовательность перестроек, переводящая $P$ в $Q$, не затрагивает этой диагонали.
Доказательство этих лемм мы оставляем читателю.
Геометрия Лобачевского и оценка $P(n)$
Итак, чтобы оценить снизу $P(n)$ достаточно оценить снизу $T(n)$. Вслед за тремя американскими математиками мы покажем, что для бесконечной последовательности значений $n$ выполнено неравенство $T(n)\ge2n-10$, т. е. что имеется гамильтонова триангуляция сферы с $n$ вершинами, которую нельзя заклеить менее чем $2n-10$ тетраэдрами. Тем самым будет доказано, что оценка задачи М1170, в) является в определённом смысле точной.
Рассмотрим многогранник $M$ с вершинами в вершинах триангуляции и настоящие геометрические тетраэдры с теми же вершинами, что и криволинейные тетраэдры, которыми мы заклеили данную триангуляцию. Тогда, конечно, суммарный объём построенных геометрических тетраэдров будет не меньше, чем объём $V$ многогранника $M$. Если теперь вспомнить, что существует максимальный объём тетраэдра, вписанного в данную сферу — $V_0$, то мы получим, что количество тетраэдров не меньше чем $\dfrac{V}{V_0}$. Увы, это рассуждение не даёт нам хорошей оценки. Более того, поскольку объём многогранника $M$ не превосходит объёма всего шара, который, в свою очередь, не превосходит $10V_0$, этот метод оценки не даёт нам даже неравенства $P(n)\ge n-3$. Но можно попытаться изменить само определение объёма так, чтобы объём шара стал бесконечным, а объём любого вписанного в него тетраэдра оставался ограниченным некоторой фиксированной величиной $V_0$. Тогда, подгоняя многогранник $M$ к шару, можно рассчитывать, что объём $M$ — и оценка $T(n)$ — будет расти достаточно быстро вместе с ростом числа вершин $n$. Вот тут и приходит на помощь неевклидова геометрия Лобачевского. Дело в том, что внутренность шара при соответствующем определении расстояния между точками превращается в модель пространства Лобачевского. Есть даже два способа это сделать. При одном способе прямыми служат хорды шара — это «модель Клейна», при другом — дуги окружностей, перпендикулярных поверхности шара, — это «модель Пуанкаре» («Квант» рассказывал о ней в одноимённой статье К. Л. Самарова и В. М. Уроева в № 6 за 1984 г.). Неевклидов объём всего шара (т. е. всего пространства Лобачевского), естественно, бесконечен, а у тетраэдра — ограничен некоторой постоянной $V_0$. А это то, что нам нужно.
Осталось только одно: найти такую гамильтонову триангуляцию сферы, что соответствующий ей многогранник с $n$ вершинами будет иметь объём, не меньший чем $(2n-10)V_0$. Это удаётся сделать (однако не для всех $n$) с помощью очень красивой конструкции. Возьмём один из пяти правильных многогранников — икосаэдр (рис. 7, а), у которого 20 треугольных граней, 12 вершин и 30 рёбер, вписанный в нашу сферу, и разобьём каждую из его граней на $k^2$ маленьких равносторонних треугольничков (см. рис. 7, б). Полученная триангуляция поверхности икосаэдра проецируется на сферу. Получается триангуляция сферы с $n=10k^2+2$ вершинами (проверьте, что она гамильтонова; часть этой триангуляции вблизи вершины икосаэдра показана на рисунке 8). Она определяет некоторый неевклидов многогранник, и после тщательных и довольно сложных вычислений оказывается, что объём этого многогранника не меньше чем $2nV_0-C_1\ln n$, где $C_1$ — некая константа. Таким образом, мы получаем неравенство $P(n)\ge 2n-C_2\ln n$, а это уже очень существенное продвижение. Используя ту же триангуляцию сферы, Слейтору, Тарьяну и Тёрстону удалось доказать и более точное неравенство $P(n)\ge 2n-10$, но только при достаточно больших $n$ вида $10k^2+2$. Таким образом, перед нами остаются две проблемы: а) доказать, что $P(n)\ge 2n-10$ при всех $n\gt12$ (или опровергнуть это); б) найти элементарное, комбинаторное доказательство изложенных выше фактов.
Рисунок номер 7
Рисунок номер 8
Может быть, кому-то из читателей «Кванта» удастся решить одну из этих задач. Попробуйте свои силы!
