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

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

Условие

Нескольким детям дали по карандашу одного из трех цветов. Дети как-то поменялись карандашами, после чего у каждого оказался не тот карандаш, который был у него вначале. Докажите, что цвета карандашей могли быть такими, что у каждого вначале и в конце карандаши были разных цветов.

Подсказка

Каждый сложный обмен есть объединение нескольких обменов по циклу.

Решение

Пусть карандаш, который был вначале у некоторого ребенка А, достался в конце ребенку B, карандаш, который был вначале у некоторого ребенка B, достался в конце ребенку C и т.д. Таким образом, когда-нибудь мы дойдем до ребенка Z, карандаш которого достался в конце ребенку А. Таким образом, группа детей A, B, C, ... , Z совершила циклический обмен карандашами; можно считать, что остальные дети в этом обмене не участвовали. Если есть дети помимо A, B, C, ... , Z, начнем новый цикл и т.д. Таким образом, каждый обмен представляется в виде нескольких циклических обменов. Теперь достаточно решить задачу для циклического обмена. Если в цикле A, B, C, ... , Z четное число детей, то раздадим вначале через одного красные карандаши, а затем оставшимся - синие. После циклического обмена каждый получит карандаш цвета, отличного от того, что был вначале. Если в цикле A, B, C, ... , Z нечетное число детей, то дадим ребенку А зеленый карандаш, дальше раздадим через одного, начиная с B, красные карандаши, а затем оставшимся - синие. Как нетрудно видеть, снова после циклического обмена каждый получит карандаш цвета, отличного от того, что был вначале.

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

web-сайт
задача

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

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