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