Во вчерашней серии футурамы поставили довольно интересную задачку — не мог не удержаться и не разобрать ее тут.
![image](https://habrastorage.org/r/w1560/storage/habraeffect/ad/c3/adc38bffe60ec3e71a3076563101eda9.png)
Итак, фабула такова: Профессор изобрел машину для обмена телами, которая, как оказалось, работает только в одну сторону. После нескольких перестановок герои оказались в тяжелой ситуации, в которой им предстояло придумать способ вернуться обратно в свои тела. Вот тут-то нам и поможет «чистая математика».
Итак, приступим. Пусть
— это цикл длины k на множестве [n] = {1… n}. Без потери общности запишем:
![\pi=\begin{pmatrix} 1 & 2 & 3 & ... & k & k+1 & ... & n\\ 2 & 3 & 4 & ... & 1 & k+1 & ... & n \end{pmatrix}](https://habrastorage.org/getpro/habr/post_images/f67/7ff/e2b/f677ffe2bdce6728ac079b49658d4790.gif=\begin{pmatrix} 1 & 2 & 3 & ... & k & k+1 & ... & n\\ 2 & 3 & 4 & ... & 1 & k+1 & ... & n \end{pmatrix})
Пусть теперь (a, b) представляет собой транспозицию, которая меняет местами содержимое a и b.
По предположению,
получена с помощью определенных подстановок над [n].
Введем два «новых тела» {x, y} и запишем
![\pi^{*}=\begin{pmatrix} 1 & 2 & 3 & ... & k & k+1 & ... & n & x & y\\ 2 & 3 & 4 & ... & 1 & k+1 & ... & n & x & y \end{pmatrix}](https://habrastorage.org/getpro/habr/post_images/f67/7ff/e2b/f677ffe2bdce6728ac079b49658d4790.gif^{*}=\begin{pmatrix} 1 & 2 & 3 & ... & k & k+1 & ... & n & x & y\\ 2 & 3 & 4 & ... & 1 & k+1 & ... & n & x & y \end{pmatrix})
Для любых i = 1,… k запишем
как ряд перестановок:
![\sigma =((x,1)(x,2)...(x,i))((y,i+1)(y,i+2)(y,k))((x,i+1))((y,1))](https://habrastorage.org/getpro/habr/post_images/b53/408/ea7/b53408ea73e02035b48e22f11b54f574.gif =((x,1)(x,2)...(x,i))((y,i+1)(y,i+2)(y,k))((x,i+1))((y,1)))
Заметим, что транспозиции меняют элемент из [n] с каким-либо элементом из {x, y}, поэтому все транспозиции отличаются от оных, образовавших исходную подстановку
, а также от транспозиции (x, y). Простой проверкой получаем:
![\pi^* \sigma = \begin{pmatrix} 1 & 2 & ... & n & x & y \\ 1 & 2 & ... & n & y & x \end{pmatrix}](https://habrastorage.org/getpro/habr/post_images/f67/7ff/e2b/f677ffe2bdce6728ac079b49658d4790.gif^* \sigma = \begin{pmatrix} 1 & 2 & ... & n & x & y \\ 1 & 2 & ... & n & y & x \end{pmatrix})
Таким образом,
инвертирует цикл длины k, оставляя x и y переставленными без использования транспозиции (x, y).
Теперь пусть
— случайная подстановка; она распадается на композицию независимых циклов, каждый из которых может быть инвертирован с использованием полученного выше алгоритма, после чего при необходимости можно поменять местами x и y, используя транспозицию (x, y).
Так-то. А вы говорите, что у дискретки нет применений IRL.
![image](https://habrastorage.org/storage/habraeffect/ad/c3/adc38bffe60ec3e71a3076563101eda9.png)
Итак, фабула такова: Профессор изобрел машину для обмена телами, которая, как оказалось, работает только в одну сторону. После нескольких перестановок герои оказались в тяжелой ситуации, в которой им предстояло придумать способ вернуться обратно в свои тела. Вот тут-то нам и поможет «чистая математика».
Итак, приступим. Пусть
![\pi](https://habrastorage.org/getpro/habr/post_images/f67/7ff/e2b/f677ffe2bdce6728ac079b49658d4790.gif)
![\pi=\begin{pmatrix} 1 & 2 & 3 & ... & k & k+1 & ... & n\\ 2 & 3 & 4 & ... & 1 & k+1 & ... & n \end{pmatrix}](https://habrastorage.org/getpro/habr/post_images/f67/7ff/e2b/f677ffe2bdce6728ac079b49658d4790.gif=\begin{pmatrix} 1 & 2 & 3 & ... & k & k+1 & ... & n\\ 2 & 3 & 4 & ... & 1 & k+1 & ... & n \end{pmatrix})
Пусть теперь (a, b) представляет собой транспозицию, которая меняет местами содержимое a и b.
По предположению,
![\pi](https://habrastorage.org/getpro/habr/post_images/f67/7ff/e2b/f677ffe2bdce6728ac079b49658d4790.gif)
Введем два «новых тела» {x, y} и запишем
![\pi^{*}=\begin{pmatrix} 1 & 2 & 3 & ... & k & k+1 & ... & n & x & y\\ 2 & 3 & 4 & ... & 1 & k+1 & ... & n & x & y \end{pmatrix}](https://habrastorage.org/getpro/habr/post_images/f67/7ff/e2b/f677ffe2bdce6728ac079b49658d4790.gif^{*}=\begin{pmatrix} 1 & 2 & 3 & ... & k & k+1 & ... & n & x & y\\ 2 & 3 & 4 & ... & 1 & k+1 & ... & n & x & y \end{pmatrix})
Для любых i = 1,… k запишем
![\sigma](https://habrastorage.org/getpro/habr/post_images/b53/408/ea7/b53408ea73e02035b48e22f11b54f574.gif)
![\sigma =((x,1)(x,2)...(x,i))((y,i+1)(y,i+2)(y,k))((x,i+1))((y,1))](https://habrastorage.org/getpro/habr/post_images/b53/408/ea7/b53408ea73e02035b48e22f11b54f574.gif =((x,1)(x,2)...(x,i))((y,i+1)(y,i+2)(y,k))((x,i+1))((y,1)))
Заметим, что транспозиции меняют элемент из [n] с каким-либо элементом из {x, y}, поэтому все транспозиции отличаются от оных, образовавших исходную подстановку
![\pi](https://habrastorage.org/getpro/habr/post_images/f67/7ff/e2b/f677ffe2bdce6728ac079b49658d4790.gif)
![\pi^* \sigma = \begin{pmatrix} 1 & 2 & ... & n & x & y \\ 1 & 2 & ... & n & y & x \end{pmatrix}](https://habrastorage.org/getpro/habr/post_images/f67/7ff/e2b/f677ffe2bdce6728ac079b49658d4790.gif^* \sigma = \begin{pmatrix} 1 & 2 & ... & n & x & y \\ 1 & 2 & ... & n & y & x \end{pmatrix})
Таким образом,
![\sigma](https://habrastorage.org/getpro/habr/post_images/b53/408/ea7/b53408ea73e02035b48e22f11b54f574.gif)
Теперь пусть
![\pi](https://habrastorage.org/getpro/habr/post_images/f67/7ff/e2b/f677ffe2bdce6728ac079b49658d4790.gif)
Так-то. А вы говорите, что у дискретки нет применений IRL.