Ghost Leg
From Wikipedia, the free encyclopedia
 |
This article may require cleanup to meet Wikipedia's quality standards. Please improve this article if you can. (February 2007) |
Ghost Leg (Chinese: 畫鬼腳), known in Japan as Amidakuji (阿弥陀籤), is a method of lottery designed to create random pairings between two sets of any number of things, as long as the number of elements in each set is the same. This is often used to distribute things among people, where the number of things distributed is the same as the number of people. For instance, chores or prizes could be assigned fairly and randomly this way.
It consists of some horizontal lines and vertical lines. Very often the number of vertical lines is the same as the number of people playing, and at the bottom lines there are certain items, e.g. things that will be given to the player. Unlike vertical lines, the number of horizontal lines can be zero or more. The horizontal lines can be drawn anywhere between two vertical lines, except that no horizontal lines crossing vertical ones. The general rule for playing this game is: first choose a line on the top, and follow this line downwards. If a horizontal line is encountered, follow the horizontal line to get to another vertical line and go downwards again. Repeat the above procedures until reaching the end of the vertical line. Then the player will be given the thing written at the bottom of the line.
If the elements written above the Ghost Leg are treated as a sequence, and after the Ghost Leg, these elements are of different order, and the sequence has been transformed to another permutation. Hence, Ghost Leg can be treated as a kind of permutating operator.
Contents |
[edit] Process
As an example, consider assigning roles in a play to actors.
- To start with, the two sets are enumerated horizontally across a board. The actors' names would go on top, and the roles on the bottom. Then, vertical lines are drawn connecting each actor with the role directly below it.
- The names of the actors and/or roles are then concealed so that people do not know which actor is on which line, or which role is on which line.
- Next, each actor adds a horizontal line to the board. Each line must connect two adjacent vertical lines, and must not directly touch any other horizontal line.
- Once this is done, the vertical lines are traced from top to bottom. As you follow the line down, if you come across a horizontal line, you follow it to the adjacent vertical line on the left or right, then resume tracing down. You continue until you reach the bottom of a vertical line, and the top item you started from is now paired with the bottom item you ended on.
Another process involves creating the ladder beforehand, then concealing it. Then people take turns choosing a path to start from at the top. If no part of the amidakuji is concealed, then it is possible to fix the system so that you are guaranteed to get a certain pairing, thus defeating the idea of random chance.
[edit] Mathematics
Part of the appeal for this game is that, unlike random chance games like rock, paper, scissors, amidakuji will always create a 1:1 correspondence, and can handle arbitrary numbers of pairings (although pairing sets with only two items each would be fairly boring). It is guaranteed that two items at the top will never have the same corresponding item at the bottom, nor will any item on the bottom ever lack a corresponding item at the top.
It also works regardless of how many horizontal lines are added. Each person could add one, two, three, or any number of lines, and the 1:1 correspondence would remain. The more lines that are added, the more random the final outcome is.
One way of realizing how this works is to consider analogy of coins in cups. You have n coins in n cups, representing the items at the bottom of the amidakuji. Then, each horizontal bar that is added represents swapping the position of two adjacent cups. Thus, it is obvious that in the end there will still be n cups, and each cup will have one coin, regardless of how many swaps you perform.
[edit] Properties
[edit] Permutation
Ghost Leg can transform the sequence of the input elements into a different order at the output. Thus, it is a permutation operator.
[edit] Periodicity
For any Ghost Leg, after implementing it for a finite number of times, the input sequence will become identical to the output sequence.
i.e. Let M be a matrix representing a particular ghost leg Mn=I for some finite n
[edit] Reversibility
For any ghost leg M, there must exist a ghost leg M-1, such that M M-1=I
[edit] Odd/Even property of permutation
As each Leg represent one permutation, the number of legs indicates the odd/even permutation property of the ghost leg.
i.e. odd number of legs = odd permutation
[edit] Infinite Ghost Legs with same permutation
Every permutation must be possible to be expressed as a Ghost Leg, but a particular permutation does not correspond to a unique ghost leg. There are infinite number of Ghost Legs representing the same permutation.
[edit] Prime
As there are infinite number of Ghost Legs representing the same permutation, it is obvious those Ghost Legs are with some kinds of equivalence. Among those equivalent Ghost Legs, the one(ones) which have smallest number of legs are called Prime.
[edit] Bubble sort and Highest Simplicity
Ghost Leg can be construced arbitrarily, but they are not necessarily to be Prime. It is proved that only those ghost legs constructed by Bubble sort contains the least number of legs, and hence Prime.
[edit] Maximum number of legs of Prime
For a permutation with n elements, the maximum number of neighbour exchanging = 
In the same way, the maximum number of legs in a Prime with n Tracks =
[edit] Bubblization
For an arbitrary Ghost Leg, it is possible to transform it into Prime by a procedure called Bubblization. When Bubblization operates, the following 2 identites are continuously applied in order to move and eliminate "useless" legs.
= 
= 
When the two identities cannot be applied any more, the ghost leg is proved to be exactly the same as the ghost leg constructed by Bubble sort, thus Bubblization can reduce ghost legs to Primes.
[edit] Randomness
Ghost Leg is not a good random permutation generator. When the number of legs is fixed and the legs are added randomly, the probability of getting different permutation is uneven. For example, if the number of legs is 3 and number of tracks is 4, the probability of getting 
is larger than that of 
.
[edit] Games
Konami produced an arcade game named Amidar which uses an Amidakuji board and rules as a setting for a Pac-Man/Qix like game.
New Super Mario Bros. and Wario: Master of Disguise feature an Amidakuji-style minigame in which the player uses the stylus to trace lines that will lead the character down the right path.
