|
Название задачи: Обмены квартир. |
 |
Условие
В некотором городе разрешаются только парные обмены квартир (если две семьи
обмениваются квартирами, то в тот же день они не имеют права участвовать в
другом обмене). Докажите, что любой сложный обмен квартирами можно осуществить за два дня.
(Предполагается, что при любых обменах каждая семья как до, так и после обмена занимает одну квартиру, и что семьи при этом сохраняются).
Решение
Сложный обмен квартир представляет собой цикл. Представим его в виде поворота правильного многоугольника, вершины которого соответствуют участвующим в обмене квартирам. Этот поворот есть композиция двух осевых симметрий (относительно серединных перпендикуляров к двум соседним сторонам). Каждая осевая симметрия задаёт несколько парных обменов; все их можно осуществить за один день.
Замечания
1. 5 баллов.
2. Задача предлагалась также на 53-й Ленинградской олимпиаде (1987, 8 кл., зад. 4).
