Ghost Leg

From Wikipedia, the free encyclopedia

Ghost Leg (Chinese: 畫鬼腳) is a game. It is often used to arrange or select things. 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.

An example of Ghost Leg:

One player's route when playing Ghost Leg:

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 1 Definition 1.1 Track (軌) 1.2 Leg (腳) 1.3 Prime 2 Representation Method 2.1 Graphical Representation 2.2 Cyclic Permutation Representation 2.3 Matrix Representation 3 Properties 3.1 Permutation 3.2 Periodicity 3.3 Reversibility 3.4 Odd/Even property of permutation 3.5 Infinite Ghost Legs with same permutation 4 Prime 4.1 Bubble sort and Highest Simplicity 4.2 Maximum number of legs of Prime 4.3 Bubblization 5 Randomness 6 Conclusion

[edit] Definition

[edit] Track (軌)

Tracks are vertical lines in Ghost Leg.

[edit] Leg (腳)

Legs are horizontal lines in Ghost Leg.

[edit] Prime

Ghost Leg with the smallest number of legs to represent a partiuclar permutation.

[edit] Representation Method

[edit] Graphical Representation

The traditional way of representation involves horizontal and vertical lines.

[edit] Cyclic Permutation Representation

Each leg represent a cyclic permutation of two elements.

For example, the example of Ghost Leg in "Introduction" can be represented by: (1 2)(2 3)(3 4)(2 3)(3 4) = (1 2 3 4)(2 3 4) .

[edit] Matrix Representation

As Ghost Leg is a permutation, it can be represented by matrices.

=

[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 Mⁿ=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 continously applied in order to move and eliminate "useless" legs.

1. =
2. =

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] Conclusion

Ghost Leg is a game with a long history. Traditionally, it was treated as a randomness generator, just like dices.

But it is possible to be analysed in a rigorous mathematical way.