Олимпиадная задача про парные обмены квартирами: доказательство для 8-10 классов
В некотором городе разрешаются только парные обмены квартир (если две семьи обмениваются квартирами, то в тот же день они не имеют права участвовать в другом обмене). Докажите, что любой сложный обмен квартирами можно осуществить за два дня.
(Предполагается, что при любых обменах каждая семья как до, так и после обмена занимает одну квартиру, и что семьи при этом сохраняются).
Разобрать решение
Сложный обмен квартир представляет собой цикл. Представим его в виде поворота правильного многоугольника, вершины которого соответствуют участвующим в обмене квартирам. Этот поворот есть композиция двух осевых симметрий (относительно серединных перпендикуляров к двум соседним сторонам). Каждая осевая симметрия задаёт несколько парных обменов; все их можно осуществить за один день.
Обсуждение
0Комментариев пока нет.