Во вчерашней серии футурамы поставили довольно интересную задачку — не мог не удержаться и не разобрать ее тут.


Итак, фабула такова: Профессор изобрел машину для обмена телами, которая, как оказалось, работает только в одну сторону. После нескольких перестановок герои оказались в тяжелой ситуации, в которой им предстояло придумать способ вернуться обратно в свои тела. Вот тут-то нам и поможет «чистая математика».

Итак, приступим. Пусть — это цикл длины k на множестве [n] = {1… n}. Без потери общности запишем:


Пусть теперь (a, b) представляет собой транспозицию, которая меняет местами содержимое a и b.
По предположению, получена с помощью определенных подстановок над [n].

Введем два «новых тела» {x, y} и запишем


Для любых i = 1,… k запишем как ряд перестановок:


Заметим, что транспозиции меняют элемент из [n] с каким-либо элементом из {x, y}, поэтому все транспозиции отличаются от оных, образовавших исходную подстановку , а также от транспозиции (x, y). Простой проверкой получаем:

Таким образом, инвертирует цикл длины k, оставляя x и y переставленными без использования транспозиции (x, y).

Теперь пусть — случайная подстановка; она распадается на композицию независимых циклов, каждый из которых может быть инвертирован с использованием полученного выше алгоритма, после чего при необходимости можно поменять местами x и y, используя транспозицию (x, y).

Так-то. А вы говорите, что у дискретки нет применений IRL.