В домашнем задании для моей программы STEP я предложил следующую задачу-головоломку.
Задача. У моих мудрецов на головах шляпы разных цветов. Как и в стандартных задачах со шляпами, они видят цвет шляп всех остальных. В отличие от многих других задач со шляпами, они также знают цвет своей шляпы. Я объявляю, какой цвет каждый из них должен в итоге надеть; это распределение — перестановка исходных цветов. Каждому мудрецу разрешено один раз поменять шляпу с кем-то другим за день. У них есть два дня, чтобы переставить шляпы так, чтобы у каждого оказался правильный цвет. Могут ли они это сделать?
Многие студенты заметили, что перестановку можно разложить на непересекающиеся циклы, и предложили решать задачу цикл за циклом. Некоторые из них даже довели эту идею до полного решения. Однако никто из них не связал задачу с темой, которую мы обсуждали в классе: диэдральные группы.
Элегантное решение
Вот элегантный способ завершить решение, если перестановка разложена на циклы.
Циклическую перестановку на $n$ элементах можно рассматривать как вращение $n$-угольника. Любое вращение $n$-угольника можно записать как произведение двух отражений. Каждое отражение $n$-угольника, рассматриваемое как перестановка, состоит только из 1- и 2-циклов. 🎉