Discrete mathematics in the "domestic" application

In yesterday's series, the futurama posed a rather interesting puzzle — I couldn't help but hold out and disassemble it here.


So, the plot is as follows: The professor invented a machine for the exchange of bodies, which, as it turned out, works only in one direction. After several permutations, the heroes found themselves in a difficult situation in which they had to figure out a way to return to their bodies. This is where pure mathematics will help us.

So let's get started. Let be Is a cycle of length k on the set [n] = {1 ... n} . Without loss of generality, we write:


Now suppose (a, b) is a transposition that interchanges the contents of a and b .
By assumption obtained by using certain substitutions over [n] .
')
We introduce two "new bodies" {x, y} and write


For any i = 1, ... k we write as a series of permutations:


Note that transpositions change an element from [n] with some element from {x, y} , therefore all transpositions differ from the ones that formed the original permutation , and also from transposition (x, y) . By a simple check we get:

In this way, inverts a cycle of length k , leaving x and y interchanged without using the transposition (x, y) .

Now let - random substitution; it splits into a composition of independent cycles, each of which can be inverted using the algorithm obtained above, after which, if necessary, you can swap x and y using the transposition (x, y) .

So that. And you say that the discrete has no IRL applications.