|
|
 |
Условие
Даны выпуклый многоугольник $M$ и простое число $p$. Оказалось, что существует ровно $p$ способов разбить $M$ на равносторонние треугольники со стороной 1 и квадраты со стороной 1.
Докажите, что длина одной из сторон многоугольника $M$ равна $p$ – 1.
Решение
Назовём каёмкой разбиения квадраты и треугольники, имеющие хотя бы одну общую точку с границей многоугольника $M$. Обозначим через $M_1$ многоугольник, полученный из $M$ отбрасыванием каёмки. Сделаем несколько наблюдений о каёмке.
1) Рассмотрим какой-нибудь угол многоугольника $M$. Поскольку он покрывается одним или несколькими углами правильных треугольников и квадратов, то он может быть равен 60°, 90°, 120°, 150°. Отсюда каждый внешний угол многоугольника не меньше 30°. Но сумма внешних углов выпуклого многоугольника равна 360°. Поэтому у многоугольника $M$ не более 12 углов, причём их может быть 12 только в случае, если все углы $M$ равны 150°.
2) Рассмотрим квадрат или треугольник каёмки, примыкающий к углу, сторона которого лежит на стороне многоугольника. Если это квадрат (см. рис. слева), то несложно видеть, что все оставшиеся фигуры разбиения, которые примыкают к этой стороне, – тоже квадраты, потому что образующиеся углы 90° можно замостить только квадратом (см. рис. справа).
Если это треугольник (см. рис. ниже слева), то несложно видеть, что все оставшиеся фигуры разбиения, которые примыкают к этой стороне, – тоже треугольники, потому что образующиеся углы 120° можно замостить только двумя треугольниками (см. рис. ниже справа). Таким образом, к каждой стороне многоугольника $M$ примыкают либо только квадраты, либо только треугольники.
3) Из предыдущего пункта следует, что стороны $M_1$ будут параллельны соответствующим сторонам $M$ (стороны $AB$ и $CD$ на рисунках). Если у $M$ нет углов по 60° или 90°, то длины сторон $M_1$ будут либо равны соответствующим длинам сторон $M$ (в случае квадратов), либо на 1 меньше (в случае треугольников). При этом длина стороны может стать равной 0. То есть $M_1$ – выпуклый многоугольник, у которого сторон не больше, чем у $M$.
Назовём характеристикой многоугольника $M$ набор чисел $(a_1, a_2, ..., a_{12})$, построенный следующим образом. Если $M$ – 12-угольник, то это длины сторон $M$, перечисленные в порядке обхода против часовой стрелки. Если у $M$ меньше 12 сторон, то не все его углы равны 150°. Мысленно добавим несколько сторон нулевой длины: если есть угол 120°, то добавим в соответствующую вершину сторону нулевой длины, если есть угол 90°, то добавим в соответствующую вершину две последовательные стороны нулевой длины, если есть угол 60° – три последовательные стороны нулевой длины. Несложно проверить, что в итоге получится 12 сторон, некоторые из которых равны 0. Стороны $a_1, a_3, ..., a_{11}$ будем называть нечётными, а стороны $a_2, a_4, ..., a_{12}$ – чётными.
Многоугольнику $M_1$ можно поставить в соответствие набор, построенный по тем же правилам, так, чтобы нумерации сторон в $M$ и $M_1$ соответствовали друг другу. Посмотрим, как могут быть связаны характеристики $M$ и $M_1$.
1) Пусть длины сторон $M$ отличны от нуля. Тогда все углы $M$ равны 150°. Заметим, что существует два варианта расположить квадрат и треугольник, примыкающие к углу 150° (см. рис.).
При выборе одного из вариантов остальная каёмка восстанавливается однозначно. Действительно, сначала восстанавливается часть каёмки, примыкающая к сторонам угла, затем разбиения двух соседних углов и т.д.
Итого получается два варианта каёмки: равносторонние треугольники расположены вдоль всех нечётных сторон, а квадраты – вдоль всех чётных; или наоборот. В первом варианте характеристикой $M_1$ будет набор $(a_1 - 1, a_2, a_3 - 1, a_4, ..., a_{11} - 1, a_{12})$, а во втором – набор $(a_1, a_2 - 1, a_3, a_4 - 1, ..., a_{11}, a_{12} - 1)$.
2) Пусть по крайней мере одна нечётная сторона $M$ равна нулю, а все чётные стороны отличны от нуля. Рассмотрим такое $i$, что $a_i$ = 0. Тогда угол при соответствующей вершине многоугольника $M$ будет равен 120° (поскольку $a_{i-1}$ и $a_{i+1}$ не равны 0), то есть его единственным образом можно разбить на два равносторонних треугольника. Далее каёмка восстанавливается однозначно. Действительно, достаточно возле всех сторон с нечётными номерами и ненулевой длиной разместить равносторонние треугольники, а возле сторон с чётными номерами и ненулевой длиной – квадраты. Получаем, что характеристика $M_1$ будет равна $(a_1, a_2 - 1, a_3, a_4 - 1, ..., a_{11}, a_{12} - 1)$.
3) Пусть по крайней мере одна чётная сторона $M$ равна нулю, а все нечётные стороны отличны от нуля. Аналогично получаем, что характеристика $M_1$ будет равна $(a_1 - 1, a_2, a_3 - 1, a_4, ..., a_{11} - 1, a_{12})$.
4) Пусть по крайней мере одна чётная и одна нечётная стороны $M$ равны нулю. Поскольку все ненулевые стороны $M_1$ параллельны соответствующим сторонам $M$ и имеют такую же или меньшую длину, то по крайней мере одна чётная и одна нечётная стороны $M_1$ равны нулю.
Отметим, что если по крайней мере одна чётная и одна нечётная стороны $M$ равны нулю, то существует не более одного способа разбить $M$ нужным образом. Действительно, тогда у $M$ найдётся угол, меньший 150°, разбиение которого восстанавливается однозначно. Далее каёмка восстанавливается не более чем одним способом. У многоугольника, полученного отбрасыванием каёмки, каёмка снова восстанавливается не более чем одним способом и т.д.
Обозначим $x = \min\{a_1, a_3, ..., a_{11}\}, y = \min\{a_2, a_4, \ldots, a_{12}\}$. Одно из чисел $x$ или $y$ отлично от нуля, иначе $M$ можно разбить не более чем одним способом. Выделим у многоугольника $M$ каёмку, уменьшающую либо чётные, либо нечётные стороны $M$ (если одно из чисел $x$ или $y$ равно 0, то каёмку можно выбрать единственным способом). Уберём каёмку, останется многоугольник $M_1$. Выделим какую-нибудь каёмку многоугольника $M_1$, уберём её и обозначим оставшийся многоугольник через $M_2$. Будем продолжать так до тех пор, пока хотя бы одна чётная и хотя бы одна нечётная стороны не станут равны нулю. В этот момент характеристика многоугольника будет равна $(a_1 - x, a_2 - y, a_3 - x, a_4 - y, ..., a_ {11} - x, a_ {12} - y)$.
Оставшийся многоугольник $M_{x+y}$ не зависит от того, какие именно каёмки были выбраны на предыдущих шагах, поскольку характеристика задаёт не более чем один многоугольник. Поэтому если $M_{x+y}$ нельзя разбить на правильные треугольники и квадраты, то и для $M$ не существует соответствующего разбиения. Следовательно, $M_{x+y}$ можно разбить единственным образом, то есть количество разбиений $M$ равно количеству способов уменьшить оба числа $x$ и $y$ до 0, то есть $C_{\smash[b]{x+y}}^y$.
По условию задачи $C_{x+y}^y = p$, где $p$ – простое число. Докажем, что это может быть только в случае $x + y = p$ и $y = 1$. Заметим, что $x+y \geqslant p$, поскольку иначе $C_{x+y}^y$ не может делиться на $p$. Также $x$ и $y$ отличны от нуля, так как иначе $C_{x+y}^y = 1$. Тогда $C_{x+y}^y \geqslant C_{x+y}^1 = x+y \geqslant p.$ Нетрудно видеть, что равенство достигается только при $x = 1, y = p$ – 1 либо наоборот. В обоих случаях одно из чисел $a_1, a_2, ..., a_{12}$ равно $p$ – 1, что и требовалось доказать.
Замечания
12 баллов
