МОШ 2022, 9 класс, задача 6

Решение. Назовём каёмкой разбиения квадраты и треугольники, имеющие хотя бы одну общую точку с границей многоугольника . Обозначим через многоугольник, полученный из отбрасыванием каёмки. Сделаем несколько наблюдений о каёмке.

• Рассмотрим какой-нибудь угол многоугольника . Поскольку он покрывается одним или несколькими углами правильных треугольников и квадратов, то он может быть равен , , , . Отсюда каждый внешний угол многоугольника не меньше . Но сумма внешних углов выпуклого многоугольника равна . Поэтому у многоугольника не более углов, причём их может быть только в случае, если все углы равны .

• Рассмотрим квадрат или треугольник каёмки, примыкающий к углу, сторона которого лежит на стороне многоугольника. Если это квадрат (см. рис. ), то несложно видеть, что все оставшиеся фигуры разбиения, которые примыкают к этой стороне, — тоже квадраты, потому что образующиеся углы можно замостить только квадратом (см. рис. ).

Если это треугольник (см. рис. ), то несложно видеть, что все оставшиеся фигуры разбиения, которые примыкают к этой стороне, — тоже треугольники, потому что образующиеся углы можно замостить только двумя треугольниками (см. рис. ). Таким образом, к каждой стороне многоугольника примыкают либо только квадраты, либо только треугольники.

• Из предыдущего пункта следует, что стороны будут параллельны соответствующим сторонам (стороны и на рисунках). Если у нет углов по или , то длины сторон будут либо равны соответствующим длинам сторон (в случае квадратов), либо на меньше (в случае треугольников). При этом длина стороны может стать равной . То есть — выпуклый многоугольник, у которого сторон не больше, чем у .

Назовём характеристикой многоугольника набор чисел , построенный следующим образом. Если — -угольник, то это длины сторон , перечисленные в порядке обхода против часовой стрелки. Если у меньше сторон, то не все его углы равны . Мысленно добавим несколько сторон нулевой длины: если есть угол , то добавим в соответствующую вершину сторону нулевой длины, если есть угол , то добавим в соответствующую вершину две последовательные стороны нулевой длины, если есть угол — три последовательные стороны нулевой длины. Несложно проверить, что в итоге получится сторон, некоторые из которых равны . Стороны , , , будем называть нечётными, а стороны , , , — чётными.

Многоугольнику можно поставить в соответствие набор, построенный по тем же правилам, так, чтобы нумерации сторон в и соответствовали друг другу. Посмотрим, как могут быть связаны характеристики и .

• Пусть длины сторон отличны от нуля. Тогда все углы равны . Заметим, что существует два варианта расположить квадрат и треугольник, примыкающие к углу (см. рис. ).

При выборе одного из вариантов остальная каёмка восстанавливается однозначно. Действительно, сначала восстанавливается часть каёмки, примыкающая к сторонам угла, затем разбиения двух соседних углов и т. д.

Итого получается два варианта каёмки: равносторонние треугольники расположены вдоль всех нечётных сторон, а квадраты — вдоль всех чётных; или наоборот. В первом варианте характеристикой будет набор , а во втором — набор .

• Пусть по крайней мере одна нечётная сторона равна нулю, а все чётные стороны отличны от нуля. Рассмотрим такое, что . Тогда угол при соответствующей вершине в многоугольнике будет равен (поскольку и не равны ), то есть его единственным образом можно разбить на два равносторонних треугольника. Далее каёмка восстанавливается однозначно. Действительно, достаточно возле всех сторон с нечётными номерами и ненулевой длиной разместить равносторонние треугольники, а возле сторон с чётными номерами и ненулевой длиной — квадраты. Получаем, что характеристика будет равна .

• Пусть по крайней мере одна чётная сторона равна нулю, а все нечётные стороны отличны от нуля. Аналогично получаем, что характеристика будет равна .

• Пусть по крайней мере одна чётная и одна нечётная стороны равны нулю. Поскольку все ненулевые стороны параллельны соответствующим сторонам и имеют такую же или меньшую длину, то по крайней мере одна чётная и одна нечётная стороны равны нулю.

Отметим, что если по крайней мере одна чётная и одна нечётная стороны равны нулю, то существует не более одного способа разбить нужным образом. Действительно, тогда у найдётся угол, меньший , разбиение которого восстанавливается однозначно. Далее каёмка восстанавливается не более чем одним способом. У многоугольника, полученного отбрасыванием каёмки, каёмка снова восстанавливается не более чем одним способом и т. д.

Обозначим и . Одно из чисел или отлично от нуля, иначе можно разбить не более чем одним способом. Выделим у многоугольника каёмку, уменьшающую либо чётные, либо нечётные стороны (если одно из чисел или равно , то каёмку можно выбрать единственным способом). Уберём каёмку, останется многоугольник . Выделим какую-нибудь каёмку многоугольника , уберём её и обозначим оставшийся многоугольник через . Будем продолжать так до тех пор, пока хотя бы одна чётная и хотя бы одна нечётная стороны не станут равны нулю. В этот момент характеристика многоугольника будет равна .

Оставшийся многоугольник не зависит от того, какие именно каёмки были выбраны на предыдущих шагах, поскольку характеристика задаёт не более чем один многоугольник. Поэтому если нельзя разбить на правильные треугольники и квадраты, то и для не существует соответствующего разбиения. Следовательно, можно разбить единственным образом, то есть количество разбиений равно количеству способов уменьшить оба числа и до , то есть .

По условию задачи , где — простое число. Докажем, что это может быть только в случае и . Заметим, что , поскольку иначе не может делиться на . Также и отличны от нуля, так как иначе . Тогда

Нетрудно видеть, что равенство достигается только при , либо наоборот. В обоих случаях одно из чисел равно , что и требовалось доказать.