ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 97936
Темы:    [ Разложение в произведение транспозиций и циклов ]
[ Композиции симметрий ]
[ Группа перестановок ]
Сложность: 3+
Классы: 8,9,10
Название задачи: Обмены квартир.
В корзину
Прислать комментарий

Условие

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


Решение

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

Замечания

1. 5 баллов.

2. Задача предлагалась также на 53-й Ленинградской олимпиаде (1987, 8 кл., зад. 4).

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1987
выпуск
Номер 10
Задача
Номер М1069
олимпиада
Название Турнир городов
Турнир
Дата 1986/1987
Номер 8
вариант
Вариант весенний тур, основной вариант, 9-10 класс
Задача
Номер 3

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .