Выбрана 1 задача 
Убрать все задачи
Дано простое число p. Назовём треугольник разрешённым, если все его углы имеют вид m/p·180°, где m целое. Одинаковыми будем считать разрешённые треугольники с одинаковым набором углов (то есть подобные). Вначале дан один разрешённый треугольник. Каждую минуту один из имеющихся треугольников разрезают на два разрешённых так, чтобы после разрезания все имеющиеся треугольники были разными. Спустя некоторое время оказалось, что ни один из треугольников так разрезать нельзя. Докажите, что к этому моменту среди имеющихся частей есть все возможные разрешённые треугольники.
|
|
 |
Условие
В таблице n×n разрешается добавить ко всем числам любого несамопересекающегося замкнутого маршрута ладьи по 1. В первоначальной таблице по диагонали стояли единицы, а остальные были нули. Можно ли с помощью нескольких разрешённых преобразований добиться того, что все числа в таблице станут равны? (Считается, что ладья побывала во всех клетках таблицы, через которые проходит её путь.)
Решение
Раскрасим таблицу в шахматном порядке. Любой удовлетворяющий условию маршрут ладьи содержит одинаковое количество белых и чёрных клеток, следовательно, разность между суммой всех "чёрных" чисел и суммой всех "белых" – инвариант. В исходной таблице эта разность не равна нулю, значит, при чётном n добиться равенства нельзя.
Для нечётного n числа сделать равными можно. Докажем это по индукции. База (n = 1) очевидна.
Шаг индукции. Разобьём таблицу на центральный квадрат (n–2)×(n–2) и рамку ширины 1. По предположению индукции можно добиться равенства чисел в центральном квадрате, не затрагивая рамку. Далее прибавим по 1 к числам внутри двух квадратов (n–1)×(n–1), не содержащих угловых единичек (подтаблицу 2×(n–1) можно обойти одним ходом ладьи, а n – 1 чётно). После этого все числа в рамке равны 1, а все числа в центральном квадрате равны между собой. Осталось несколько раз пройти ладьей по рамке.
Ответ
При чётном n нельзя, при нечётном – можно.
Замечания
4 балла
