|
|
 |
Условие
Дано простое число p. Назовём треугольник разрешённым, если все его углы имеют вид m/p·180°, где m целое. Одинаковыми будем считать разрешённые треугольники с одинаковым набором углов (то есть подобные). Вначале дан один разрешённый треугольник. Каждую минуту один из имеющихся треугольников разрезают на два разрешённых так, чтобы после разрезания все имеющиеся треугольники были разными. Спустя некоторое время оказалось, что ни один из треугольников так разрезать нельзя. Докажите, что к этому моменту среди имеющихся частей есть все возможные разрешённые треугольники.
Решение
Углы разрешенного треугольника равны i/p·180°, j/p·180°, k/p·180°. Такой треугольник будем обозначать T(i, j, k), где i + j + k = p. Для краткости будем измерять углы в единицах: когда мы говорим об угле m, то имеем в виду угол m/p·180°.
Способ 1. Предположим, j < k. Можно разрезать треугольник T(i, j, k) на два треугольника, один из которых подобен ему. Для этого нужно разрезать угол k на углы j и k – j; треугольник будет разделен на треугольники T(i, j, k) и T(i + j, j, k – j). Эта операция называется базовым делением.
Если после остановки процесса деления отсутствует треугольник T(i + j, j, k – j), то отсутствует и треугольник T(i, j, k). В противном случае допустимо сделать базовое деление треугольника T(i, j, k), получив снова T(i, j, k) и новый треугольник T(i + j, j, k – j).
Отсюда следует, что если некий треугольник отсутствует после завершения процесса деления, то любой другой треугольник, из которого можно получить этот треугольник с помощью базовых делений, также отсутствует.
Поэтому, чтобы доказать, что после завершения процесса все возможные треугольники присутствуют, достаточно доказать, что с помощью базовых делений любого треугольника можно создать любой другой.
Возьмём какой-нибудь треугольник T(i, j, k). Основные деления производятся несколько раз – если k > j, угол k заменяется на k – j, а если j > k угол j заменяется на j – k. Будем повторять эту операцию, пока не окажется, что два последних числа равны. Мы получим треугольник T(c, d, d), где d = НОД(j, k) (ибо мы применили алгоритм Евклида к j и k). При этом НОД(c, d) = 1, поскольку является делителем простого числа p = c + d + d. Следовательно, если мы повторим алгоритм Евклида, то получим треугольник (1, 1, p – 2).
Теперь отметим, что при базовом делении, если можно сформировать треугольник T(q = i + j, j, r = k – j) из треугольника T(i, j, k), то также можно создать треугольник T(i = q – j, j, k = r + j) из треугольника T(q, j, r). Следовательно, если можно из любого треугольника получить T(1, 1, p – 2), то также можно из треугольника T(1, 1, p – 2) получить любой возможный треугольник. Поэтому из любого треугольника можно получить любой другой с помощью базовых делений.
Способ 2. Разделим все разрешённые треугольники на присутствующие (имеющиеся к этому моменту) и отсутствующие, углы присутствующих треугольников тоже назовём присутствущими. Покажем, что если какой-нибудь треугольник отсутствует, допустимое разрезание найдётся. Разберём три случая.
1) Наименьший присутствующий угол i больше 1. Разрежем соответствующий треугольник, разбив угол i на углы 1 и i – 1. Полученные треугольники содержат углы, меньшие i, поэтому раньше они отсутствовали. Заметим, что эти треугольники не одинаковы: такое возможно, лишь когда мы режем T(2, m, m), но тогда p = 2 + 2m, что противоречит простоте p.
2) Угол 1 присутствует, но T(1, 1, p – 2) отсутствует. Выберем среди присутствующих треугольников вида T(1, i, j) треугольник с наименьшим углом i ≥ 2 и разрежем его по углу i на T(1, j, i) и T(i – 1, j + 1). Первый из этих треугольников подобен разрезанному, а второй отсутствовал (по выбору i).
3) T(1, 1, p – 2) присутствует. Пусть i – наименьший из углов отсутствующих треугольников. Рассмотрим все отсутствующие треугольники с углом i, отметим в них по одному углу i, а остальные углы в них назовём добавочными (они тоже могут быть равны i). Выберем среди добавочных угол j – наибольший из кратных i (если такие есть) или просто наибольший (если кратных i нет). Обозначим k = p – (i + j). Докажем, что треугольник T(i, i + j, k – i) возможен и присутствует. Действительно, угла i + j среди добавочных нет (иначе его бы выбрали вместо j). Осталось проверить неравенство k – i > 0. Заметим, что k ≥ i (по выбору i, поскольку это угол отсутствующего треугольника T(i, j, k)). Допустим, k = i. Но угол k добавочный, значит, среди добавочных есть углы, кратные i. Но тогда и j кратно i (по выбору j), и p кратно i. Значит, i = 1. Но тогда треугольник T(i, j, k) = T(1, p – 2, 1) отсутствует. Противоречие. Итак, k > i, то есть k – i > 0.
Разрезав в присутствующем треугольнике T(i, i + j, k – i) угол i + j на части i и j, можно получить отсутствовавший треугольник T(i, j, k) и треугольник, подобный разрезанному.
Итак, во всех трёх случаях допустимое разрезание нашлось.
Замечания
8 баллов
