У вчорашній серії футурами поставили досить цікаву задачку - не міг не втриматися і не розібрати її тут.
Отже, фабула така: Професор винайшов машину для обміну тілами, яка, як виявилося, працює тільки в один бік. Після кількох перестановок герої опинилися у важкій ситуації, в якій їм належало придумати спосіб повернутися назад у свої тіла. Ось тут-то нам і допоможе «чиста математика».
Отже, приступимо. Нехай - це цикл довжини 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.
