Разбиение многоугольника на треугольники и квадраты

  Назовём каёмкой разбиения квадраты и треугольники, имеющие хотя бы одну общую точку с границей многоугольника $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,  что и требовалось доказать.