Ghost leg

Did You Know?

• If the legs are drawn randomly, the evenness of the distribution of permutations increases with the number of legs.
• A given number of legs can produce at most half of all possible permutations.

Process

To begin, the two sets are listed horizontally across a board, with actors' names on top and roles on the bottom. Vertical lines connect each top item to the one directly below it, then the names or roles are concealed. Each actor adds a leg connecting two adjacent vertical lines, ensuring it does not touch any other horizontal line. A path is traced from the top of each vertical line downward; when a leg is encountered, the path follows it to the adjacent vertical line and continues until reaching the bottom. The top item is thus paired with the bottom item at the path's end. Alternatively, the ladder may be created and concealed first, then participants choose a starting path. If the amidakuji is not concealed, the system can be fixed to guarantee a certain pairing.

Mathematics

Unlike games of pure chance such as rock, paper, scissors, amidakuji always produces a one-to-one correspondence and can handle any number of pairings. No two top items will ever map to the same bottom item, and every bottom item will have a matching top item. This holds regardless of how many horizontal lines are added. One way to understand this is to imagine n coins in n cups representing the bottom items; each leg swaps two adjacent cups, so after any number of swaps, each cup still holds one coin.

Properties

A ghost leg transforms an input sequence into an output sequence of the same length, effectively acting as a permutation of n symbols. It can be represented by a permutation matrix, and applying the same ghost leg repeatedly eventually returns the original sequence. For any ghost leg with matrix M, there exists an inverse ghost leg with matrix M−1. The number of legs determines the permutation's parity: an odd number yields an odd permutation, an even number an even permutation. Every permutation can be expressed as a ghost leg, but the representation is not unique—infinitely many ghost legs produce the same permutation.

Prime

Among the infinite ghost legs representing a given permutation, those with the fewest legs are called prime. Only ghost legs constructed by bubble sort contain the fewest legs and are therefore prime, as bubble sort performs the minimum number of adjacent exchanges to sort a sequence. The maximum number of legs in a prime with n tracks equals the maximum number of neighbor exchanges for a permutation of n elements. An arbitrary ghost leg can be reduced to a prime through a procedure called bubblization, which repeatedly applies two identities to move and eliminate useless legs. When no further identities can be applied, the ghost leg matches the one built by bubble sort.