Всесиб 2025, 11 класс, задача 5

Доказательство. Разбиение выпуклого многоугольника непересекающимися
диагоналями на треугольники называется его триангуляцией. Разнообразные триангуляции
многоугольников широко изучаются в элементарной математике. Из школьной программы
известно, что любая триангуляция -угольника содержит треугольника и
использует диагонали. Эту информацию будем считать не требующей
доказательства.
Сначала покажем, как осуществить требуемую в условии триангуляцию -угольника, если делится на . Занумеруем вершины -угольника по часовой стрелке числами от до . Проведём диагонали, попарно соединяющие вершины , , для всех , они и образуют искомую триангуляцию. При этом из вершины номер выходит диагонали, из вершин , для всех по диагонали, и из вершин , и для всех - диагоналей.
Теперь докажем, что, если можно осуществить требуемую в условии триангуляцию -угольника, то делится на .
Доказательство проведём индукцией по . Триангуляцию из условия будем дальше
называть хорошей.
Базой индукции служат случаи . При сам треугольник является своей
хорошей триангуляцией с диагоналями. В случаях , есть ровно по одной
триангуляции с или диагоналями соответственно, и они, очевидно, не являются
хорошими. При имеются разных триангуляции, одна из которых хорошая, при
которой диагонали соединяют попарно три вершины, расположенных через одну, скажем,
номер , и . Таким образом, база индукции доказана.
Шаг индукции. Пусть в -угольнике можно сделать хорошую триангуляцию, а
предположение индукции верно для всех -угольников, где . Докажем, что делится на .
Назовём диагональ -угольника длинной, если по обе стороны от неё лежат по две или больше его вершин. Докажем, что любая триангуляция -угольника при содержит хотя бы одну длинную диагональ. Если это не так, то любая диагональ триангуляции отсекает от -угольника треугольник, образованный ей и двумя соседними сторонами многоугольника, причём эти пары сторон у различных диагоналей не содержат общих сторон. Следовательно, количество диагоналей в триангуляции не превосходит , а оно, как мы знаем, равно . Тогда , откуда , что противоречит рассматриваемому случаю . Таким образом, любая триангуляция -угольника при содержит хотя бы одну длинную диагональ.
Решающий шаг. Рассмотрим хорошую триангуляцию -угольника при и её
длинную диагональ , разбивающую его на два многоугольника и , в каждом из
которых не менее , и не более вершин. Диагонали исходной хорошей триангуляции
-угольника (дальше просто диагонали), кроме , образуют триангуляции
многоугольников и , причём, как мы сейчас покажем, одна из них сразу является
хорошей, а другую несложно таковой сделать.
Обозначим за и множества диагоналей триангуляции, выходящих из вершины , и попавших в многоугольники и соответственно, аналогично и - для диагоналей из . В каждой из этих пар множеств одно содержит чётное число диагоналей, а другое - нечётное. Из того, что общие количества концов диагоналей триангуляции, попавших в , и попавших в чётны, и количества концов диагоналей триангуляции, выходящих изо всех вершин, кроме и , чётны, следует, что чётны числа и . Значит, в одной из пар , и , оба числа чётны, а в другой - оба нечётны. Следовательно, в одном из многоугольников, скажем в , оставшиеся там диагонали исходной триангуляции образуют хорошую триангуляцию, а в другом - а именно в , вершинам и инцидентны нечётные количества оставшихся диагоналей исходной триангуляции, а всем остальным - чётное. Теперь добавим к многоугольнику ещё одну новую вершину,
располагающуюся между и , получив новый многоугольник . В полученном
многоугольнике оставшиеся диагонали исходной триангуляции, включая , образуют
хорошую триангуляцию, а число его вершин не превосходит . По
предположению индукции, количества и вершин в каждом из многоугольников и
соответственно, делятся на . Следовательно, и количество вершин в исходном -угольнике, равное , тоже делится на . Тройка вычитается, так как вершины и
в сумме учитываются дважды, и ещё нужно удалить добавленную к многоугольнику
новую вершину, не содержащуюся в исходном -угольнике.
Доказательство а. Обобщение идеи доказательства , тоже индукционное. Возьмём произвольную вершину многоугольника, из которой выходят не менее двух диагоналей, пусть эти диагонали соединяют с вершинами , . Они разбивают исходный многоугольник на - нечётное число частей, каждая из которых является триангулированным оставшимися диагоналями многоугольники с меньшим, чем , числом вершин. Рассуждая, как в решении , получим, что триангуляции первой, третьей, пятой,..., -ой из них (слева направо) уже являются хорошими, а во второй, четвёртой,..., -ой частях из вершин и , соответственно, выходит нечётное количество диагоналей. Эти части не могут быть просто треугольниками , вообще не содержащими внутри диагоналей, поэтому в каждой из них должна содержаться диагональ . В таком случае многоугольник, получающийся из каждой такой части удалением треугольника , уже будет хорошо триангулирован. Применяем ко всем полученным частям предположение индукции, получим, что число вершин в каждой из них делится на . В сумме количеств вершин во всех этих частях, включая треугольники вида , вершины , содержатся по раза, а вершина - раз. Следовательно, превышает количество вершин в исходном многоугольнике на . Очевидно, что делится на , поэтому и делится на , что и требовалось доказать.

Доказательство 2.** Рассмотрим хорошую триангуляцию -угольника. Хорошо
известно, что её треугольники можно раскрасить в цвета, белый и чёрный, так, что любые
два треугольника, имеющих общую сторону, окрашены в разные цвета. Этот факт легко
доказать индукцией по числу диагоналей, начав с монотонной окраски всего
многоугольника, добавляя по одной диагонали и меняя каждый раз окраску всех частей
многоугольника с одной из сторон от добавляемой диагонали на противоположный цвет.
Заметим, что, если из каждой вершины -угольника выходит чётное число
диагоналей, то каждая его сторона является стороной треугольников одного, скажем
чёрного, цвета. Тогда каждая диагональ триангуляции и каждая сторона -угольника
являются сторонами в точности одного из чёрных треугольников. Если чёрных
треугольников k штук, то , откуда следует, что 2n - делится на
. Отсюда легко следует, что и n делится на .
Доказательство 3. Рассмотрим наш триангулированный хорошим образом n -
угольник как граф, вершины которого – это вершины -угольника, а рёбра - стороны и
диагонали -угольника.
Осознаем, что вершины графа можно правильно окрасить в цвета – так, чтобы
вершины одного цвета не были соединены ребром. Проще всего это сделать по индукции.
Найдём самую короткую диагональ триангуляции, она отсекает от -угольника
треугольник, две стороны которого являются сторонами -угольника с общей вершиной . Если бы это было не так, то меньшая из двух частей, на которые рассекает -угольник
диагональ , содержала бы непроведённую диагональ труангуляции. По индукции,
вершины всего -угольника без треугольника правильно красятся в цвета.
Осталось окрасить вершину в цвет, отличный от цветов вершин и В.
Докажем, из условия следует, что вершины -угольника правильно окрашены в три цвета в циклическом порядке: , , , , , , .... Действительно, рассмотрим идущие по часовой стрелке последовательные соседние вершины -угольника , и , и все диагонали триангуляции , , ... , выходящие из вершины в их естественном порядке следования от стороны к стороне . Считаем и окрашенными в цвета и соответственно. Среди отрезков , , , ..., , любые два соседних являются двумя сторонами некоторого треугольника триангуляции, вершины которого окрашены в три различных цвета, поэтому вторые концы диагоналей , , ... окрашены по порядку в чередующиеся цвета и , причём последняя из них, ввиду чётности их количества, окрашена в цвет. Следовательно, вершина -угольника , следующая за , окрашена в цвет . Аналогично доказывается, что за вершиной цвета следует вершина цвета и т. д. Поскольку окраска правильная, замкнуться цикл по вершинам может тогда и только тогда, когда его длина делится на .