Julio
Castiñeira Merino
Foreword
The present note tries to show the relation that exits between the theorem of factoring of a permutation into cycles and an old and popular Spanish solitaire the chance solitaire [2], calculating the probability of winning. It is a cocktail with tree components, game, permutations and probability. We don’t know whether this solitaire, or a variant of it is played outside Spain. A similar one is the clock solitaire, analyzed in the Mathematics Magazine, [1], [3], and the chance solitaire could be a variant of it but playing with four clocks.
Although the Spanish deck differs from the American deck, it has forty cards and their four suits are different, we have developed the game with the American one, since it is very popular all over the world and because the reasoning and formulas can be generalized to any deck of n cards and m suits.
Description Of The Game
From a deck of fifty two cards, you place forty eigth cards face down in four horizontal rows of twelve12 cards each, keeping the remaining four cards in your hand. These four cards from now on will be called “the pile”.
The object of this game of solitaire is to put all the cards in order by successive moves, placing the clubs in the first row, diamonds in the second, spades in the third and hearts in the fourth in ascending order from the left to right, from Ace to King.
The following are the moves allowed:
R1. Any card from “the pile” in your hand, can be placed according to the previously indicated order, the card whose place it occupies is put face-up in its corresponding place. This process is repeated until a king appears.
R2. When a king comes up, either from your hand or form one of the sequences described above, you put it to the right of its corresponding Queen.
R3. Once all the possible moves have been completed, if any cards remain face-down you turn them over.
Winning the game procedure: you win if all the cards are in the order previously described, if not, you lose.
Obviously the result of the game depends solely upon the initial order of the cards. We wish to answer the following questions:
Q1. What is the
probability of winning the game?
Q2. What is the probability of winning if we have in the “pile” 0,1,2,3, or 4 kings respectively?
Mathematical Outline
Definition. - A
permutation c of a finite set C is a k-cycle or cycle of length k iff an
ordered set exits a1, a2, .... ak belonging to
C such that
The {a1,
a2, ..., ak } set is called the orbit of the k-cycle.
Let us observe that a cycle of
length one is the identity permutation. The cycles are the natural
generalization of the transpositions (2-cycles) and the cyclic permutations. To
describe a cycle it is sufficient to give the elements of its orbit and its
order. We shall call (a1, a2, ..., ak ) the
cycle whose orbit is {a1, a2, ......, ak }
It is well known that a permutation is
factored into the product of the transpositions. In a similar way a permutation
is factored into the product of its cycles, this factoring is unique except for
the order.
Theorem. Let f be a permutation of a set S with n
elements. Then
1)
2) Two different
cycles of factoring have disjoint orbits.
3) This
factoring is unique except for the order.
4) The sum of
the lengths of the factors is less than or equal to the degree of the
permutation.
Proof. Let a be an element belonging to S. If
(a,
f(a), f 2(a), f r-1(a))
Where r is the
smallest integer such that f r (a) = a. We call this cycle c1 . Choose an element b that
does not belong to the orbit of c1 and which
Repeat as many
times as possible the procedure and will find cycles c1, c2,...,
cs . It is obvious that the
orbits are disjoint and the elements that do not belong to any of the orbits of
the cycles ci are fixed with respect to f. From this we find that
By construction, any cycle leaves
the elements of the orbits of the others cycles fixed, for this reason it is
possible to permute the order of the cycles. The uniqueness is an immediate
consequence of the construction method.
We associate each hand with a set of
permutations of the set of 52 cards. To do this you only have to place the four
cards from “the pile” on the right of the column of queens. The 4! Possible
ways of doing it do not affect the result.
Each one of the cadences of
movements described in rules R1 and R2, (which starts with one card from the
pile and ends with the king that corresponds to the place that the said card
occupied initially) is a cycle whose length is the number of movements
realized.
When is a hand unfavorable? When the factorial breakdown into cycles
of any one of the 24 permutations associated with one hand, has at least a
cycle of length greater than or equal to two, such that its orbit does not
contain a king. The orbit of said cycle would be part of the cards that are
left out of order after completing the operations indicated in rule R3.
This criterion, ever though it is a mathematical feature of the problem, has two disadvantages: the first consists in that the correspondence described between the hands and the permutations is not a bijection. The second and most important disadvantage is based on the facts that you can’t realize a convenient calculation of the number of favorable cases (or of unfavorable ones).
These difficulties can be avoided using the following criterion: of
the 24 possible ways of placing the cards from the pile in each hand, we choose
the one in which initial card from the pile occupies the place of the first
king that appears in the cadence. This apparently artificial criterion
facilitates the calculation of the numbers of possible cases. But it also has a
slight disadvantage: if we really want to know the initial position that
corresponds to one hand, we must finish the game!
With the previously mentioned criterion we get the following result:
One hand of the solitaire game is favourable iff the associated permutation is a product of cycles and if there is one, and only one king in the orbit of each cycle of length greater than one.
Let f a favourable permutation, we
can see that
f = (a1, a2, ...,at , c) · (at+1, at+2, ...,aq , d) · (aq+1, aq+2, ...,ar , s) · (ar+1, ar+2, ...,ap , h)
where the ai are cards others than kings and c, d, s and h
are the kings of clubs, diamonds, spades and hearts respectively. If k is the
sum of the lengths of the cycles then the associated permutation corresponds to
a favourable hand such that 52 – k cards are into their place and which are not
moved by rules R1 and R2.
We
have to choose three places from k –1 to put the signs c) · (, d) · (, and s) · ( ; the other places must be occupied by k –4
cards different from kings. Bearing in mind that the order in the orbits is
essential, we have
Therefore we have
The
answer to the second question is realized in a similar way. If we bear in mind
the definition of conditioned probability and the following facts:
a) If
there are no kings in the pile, a hand is favourable if the associated
permutation is a product of exactly 4 cycles and the orbit of each cycle has a
king.
b) If we
do have a king (respectively 2, respectively. 3 kings) in the pile, a hand is
favourable iff the associated permutation is a product of exactly 3 cycles
(respectively 2, respectively 1 cycles) and the orbit of each cycle has a king.
Therefore:
P (To
win & no kings in the pile) =
P (To
win & there is exactly one king in the pile) =
P(To win & two kings in the pile) =
P
(To win & there are exactly three kings in the pile) =
The probability of there are exactly i kings in the
pile is
If by P (W | i-kings) we understand the probability of winning, having i-kings in the pile,
We shall obtain the following results:
i =0, 1, 2 and 3
Obviously the P (to win & there are four
kings in the pile) =
and
Is almost zero.
References
1. Ecker, Michael. How to win in the solitaire game of clock, The Mathematics Magazine 55 (1981)
2. Heraclio Fournier. Juegos de Solitarios Españoles, 1980
3. Jenkins and Muller. A probabilistic analisys of Clock Solitaire, The Mathematics Magazine 54 (1981)
4. Julio Castiñeira, Problem 1183 The Mathematics Magazine, January 1984