Let’s do the Landau shuffle

Posted on 2021/10/23 by wdjoyner

Here’s a shuffle I’ve not seen before:

Take an ordinary deck of 52 cards and place them, face up, in the following pattern:
Going from the top of the deck to the bottom, placing cards down left-to-right, put 13 cards in the top row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
11 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 9 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 7 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 5 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\$
then 3 cards in the next row:
$\Box\ \Box\ \Box\$
and finally, the remaining 4 cards in the last row:
$\Box\ \Box\ \Box\ \Box\$
Now, take the left-most card in each row and move it to the right of the others (effectively, this is a cyclic shift of that row of cards to the left).
Finally, reassemble the deck by reversing the order of the placement.

In memory of the great German mathematician Edmund Landau (1877-1938, see also this bio), I call this the Landau shuffle. As with any card shuffle, this shuffle permutes the original ordering of the cards. To restore the deck to it’s original ordering you must perform this shuffle exactly 180180 times. (By the way, this is called the order of the shuffle.) Yes, one hundred eighty thousand, one hundred and eighty times. Moreover, no other shuffle than this Landau shuffle will require more repetitions to restore the deck. So, in some sense, the Landau shuffle is the shuffle that most effectively rearranges the cards.

Left to right: Oswald Veblen, Edmund Landau, Harald Bohr. Location, photographer, date unknown.

Now suppose we have a deck of $n$ (distictly labeled) cards, where $n>2$ is an integer. The collection of all possible shuffles, or permutations, of this deck is denoted $S_n$ and called the symmetric group. The above discussion leads naturally to the following question(s).

Question: What is the largest possible order of a shuffle of this deck (and how do you construct it)?

This requires a tiny bit of group theory. You only need to know that any permutation of $n$ symbols (such as the card deck above) can be decomposed into a composition or product) of disjoint cycles. To compute the order of an element $g \in S_n$ , write that element $g$ in disjoint cycle notation. Denote the lengths of the disjoint cycles occurring in $g$ as $k_1, k_2, \dots , k_m$ , where $k_i>0$ are integers forming a partition of $n$ : $n = k_1 + k_2 +\dots + k_m$ . Then the order of $g$ is known to be given by $order(g) = LCM(k_1, k_2, ...., k_m)$ , where LCM denotes the least common multiple.

The Landau function $g(n)$ is the function that returns the maximum possible order of an element $g \in S_n$ . Landau introduced this function in a 1903 paper where he also proved the asymptotic relation $\lim_{n\to \infty} \frac{\ln(g(n))}{\sqrt{n\ln(n)}}=1$ .

Example: If $n=52$ then note $52 = 13+11+9+7+5+3+4$ and that $LCM(13,11,9,77,5,3,4)=180180$ .

Oddly, my favorite mathematical software program SageMath does not have an implementation of the Landau function, so we end with some SageMath code.

def landau_function(n):
    L = Partitions(n).list()
    lcms = [lcm(P) for P in L]
    return max(lcms)

Here is an example (the time is included to show this took about 2 seconds on my rather old mac laptop):

sage: time landau_function(52) CPU times: user 1.91 s, sys: 56.1 ms, total: 1.97 s Wall time: 1.97 s 180180

A mathematical card trick

Posted on 2021/03/28 by wdjoyner

If you search hard enough on the internet you’ll discover a pamphlet from the 1898 by Si Stebbins entitled “Card tricks and the way they are performed” (which I’ll denote by [S98] for simplicity). In it you’ll find the “Si Stebbins system” which he claims is entirely his own invention. I’m no magician, by from what I can dig up on Magicpedia, Si Stebbins’ real name is William Henry Coffrin (May 4 1867 — October 12 1950), born in Claremont New Hampshire. The system presented below was taught to Si by a Syrian magician named Selim Cid that Si sometimes worked with. However, this system below seems to have been known by Italian card magicians in the late 1500’s. In any case, this blog post is devoted to discussing parts of the pamphlet [S98] from the mathematical perspective.

In stacking the cards (face down) put the 6 of Hearts $6 \heartsuit$ first, the 9 of Spades $9 \spadesuit$ next (so it is below the $6 \heartsuit$ in the deck), and so on to the end, reading across left to right as indicted in the table below (BTW, the pamphlet [S98] uses the reversed ordering.) My guess is that with this ordering of the deck — spacing the cards 3 apart — it still looks random at first glance.

Next, I’ll present a more mathematical version of this system to illustrate it’s connections with group theory.

We follow the ordering suggested by the mnemonic CHaSeD, we identify the suits with numbers as follows: Clubs is 0, Hearts is 1, Spades is 2 and Diamonds is 3. Therefore, the suits may be identified with the additive group of integers (mod 4), namely: ${\bf{Z}}/4{\bf{Z}} = \{ 0,1,2,3 \}$ .

For the ranks, identify King with 0, Ace with 1, 2 with 2, $\dots$ , 10 with 10, Jack with 11, Queen with 12. Therefore, the ranks may be identified with the additive group of integers (mod 13), namely: ${\bf{Z}}/13{\bf{Z}}=\{ 0,1,2,\dots 12\}$ .

Rearranging the columns slightly, we have the following table, equivalent to the one above.

0	1	2	3
3	6	9	12
2	5	8	11
1	4	7	10
0	3	6	9
12	2	5	8
11	1	4	7
10	0	3	6
9	12	2	5
8	11	1	4
7	10	0	3
6	9	12	2
5	8	11	1
4	7	10	0

Mathematical version of the Si Stebbins Stack

In this way, we identify the card deck with the abelian group

$G = {\bf{Z}}/4{\bf{Z}} \times {\bf{Z}}/13{\bf{Z}}$ .

For example, if you spot the $2 \clubsuit$ then you know that 13 cards later (and If you reach the end of the deck, continue counting with the top card) is the $2 \heartsuit$ , 13 cards after that is the $2 \spadesuit$ , and 13 cards after that is the $2 \diamondsuit$ .

Here are some rules this system satisfies:

Rule 1 “Shuffling”: Never riff shuffle or mix the cards. Instead, split the deck in two, the “bottom half” as the left stack and the “top half” as the right stack. Take the left stack and place it on the right one. This has the effect of rotating the deck but preserving the ordering. Do this as many times as you like. Mathematically, each such cut adds an element of the group $G$ to each element of the deck. Some people call this a “false shuffle” of “false cut.”

Rule 2 “Rank position”: The corresponding ranks of successive cards in the deck differs by 3.

Rule 3 “Suit position”: Every card of the same denomination is 13 cards apart and runs in the same order of suits as in the CHaSeD mnemonic, namely, Clubs $\clubsuit$ , Hearts $\heartsuit$ , Spades $\spadesuit$ , Diamonds $\diamondsuit$ .

At least, we can give a few simple card tricks based on this system.

Trick 1: A player picks a card from the deck, keeps it hidden from you. You name that card.

This trick can be set up in more than one way. For example, you can either

(a) spread the cards out behind the back in such a manner that when the card is drawn you can separate the deck at that point bringing the two parts in front of you, say a “top” and a “bottom” stack, or

(b) give the deck to the player, let them pick a card at random, which separates the deck into two stacks, say a “top” and a “bottom” stack, and have the player return the stacks separately.

You know that the card the player has drawn is the card following the bottom card of the top stack. If the card on the bottom of the top stack is denoted $(a,\alpha) \in G$ and the card drawn is $(b,\beta)$ then

$b \equiv a+3 \pmod{13}, \ \ \ \ \ \ \beta \equiv \alpha +1 \pmod{4}.$

For example, a player draws a card and you find that the bottom card is the $9 \diamondsuit$ . What is the card the player picked?

solution: Use the first congruence listed: add 3 to 9, which is 12 or the Queen. Use the second congruence listed: add one to Diamond $\diamondsuit$ (which is 3) to get $0 \pmod 4$ (which is Clubs $\clubsuit$ ). The card drawn is the $Q \clubsuit$ .

Trick 2: Run through the deck of cards (face down) one at a time until the player tells you to stop. Name the card you were asked to stop on.

Place cards behind the back first taking notice what the bottom card is. To get the top card, add 3 to the rank of the bottom card, add 1 to the suit of the bottom card. As you run through the deck you silently say the name of the next card (adding 3 to the rank and 1 to the suit each time). Therefore, you know the card you are asked to stop on, as you are naming them to yourself as you go along.

MINIMOGs and Mathematical blackjack

Posted on 2017/09/30 by wdjoyner

This is an exposition of some ideas of Conway, Curtis, and Ryba on $S(5,6,12)$ and a card game called mathematical blackjack (which has almost no relation with the usual Blackjack).

Many thanks to Alex Ryba and Andrew Buchanan for helpful discussions on this post.

Definitions

An m-(sub)set is a (sub)set with m elements. For integers $k<m<n$ , a Steiner system S(k,m,n) is an n-set X and a set S of m-subsets having the property that any k-subset of X is contained in exactly one m-set in S. For example, if $X = \{1,2,\dots,12\}$ , a Steiner system S(5,6,12) is a set of 6-sets, called hexads, with the property that any set of 5 elements of X is contained in (“can be completed to”) exactly one hexad.

Rob Beezer has a nice Sagemath description of S(5,6,12).

If S is a Steiner system of type (5,6,12) in a 12-set X then any element the symmetric group $\sigma\in Symm_X\cong S_{12}$ of X sends S to another Steiner system $\sigma(S)$ of X. It is known that if S and S’ are any two Steiner systems of type (5,6,12) in X then there is a $\sigma\in Symm_X$ such that $S'=\sigma(S)$ . In other words, a Steiner system of this type is unique up to relabelings. (This also implies that if one defines $M_{12}$ to be the stabilizer of a fixed Steiner system of type (5,6,12) in X then any two such stabilizer groups, for different Steiner systems in X, must be conjugate in $Symm_X$ . In particular, such a definition is well-defined up to isomorphism.)

Curtis’ kitten

NICOLE SHENTING – Cats Playing Poker Cards

J. Conway and R. Curtis [Cu1] found a relatively simple and elegant way to construct hexads in a particular Steiner system $S(5,6,12)$ using the arithmetical geometry of the projective line over the finite field with 11 elements. This section describes this.

Let $\mathbf{P}^1(\mathbf{F}_{11}) =\{\infty,0,1,2,...,9,10\}$ denote the projective line over the finite field $\mathbf{F}_{11}$ with 11 elements. Let $Q=\{0,1,3,4,5,9\}$ denote the quadratic residues with 0, and let $L=\cong PSL(2,\mathbf{F}_{11}),$ where $\alpha(y)=y+1$ and $\beta(y)=-1/y$ . Let $S=\{\lambda(Q)\ \vert\ \lambda\in L\}.$

Lemma 1: $S$ is a Steiner system of type $(5,6,12)$ .

The elements of S are known as hexads (in the “modulo 11 labeling”).

 	 	 	 	 		 	 	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	 	 	 	6	 	 	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	 	 	2	 	10	 	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	 	5	 	7	 	3	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	6	 	9	 	4	 	6	 	 
 	 	 	 	 	 	 	 	 	 	 
 	2	 	10	 	8	 	2	 	10	 
 	 	 	 	 	 	 	 	 	 	 
0	 	 	 	 	 	 	 	 	 	1

Curtis’ Kitten.

In any case, the “views” from each of the three “points at infinity” is given in the following tables.

6	10	3
2	7	4
5	9	8
picture at 

5	7	3
6	9	4
2	10	8
picture at 	

5	7	3
9	4	6
8	2	10
picture at

Each of these $3\times 3$ arrays may be regarded as the plane $\mathbf{F}_3^2$ . The lines of this plane are described by one of the following patterns.

		
		
			
slope 0	

		
		
			
slope infinity

		
		
			
slope -1

		
		
		
slope 1

The union of any two perpendicular lines is called a cross. There are 18 crosses. The complement of a cross in $\mathbf{F}_3^2$ is called a square. Of course there are also 18 squares. The hexads are

$\{0,1,\infty\}\cup \{{\rm any\ line}\}$ ,
the union of any two (distinct) parallel lines in the same picture,
one “point at infinity” union a cross in the corresponding picture,
two “points at infinity” union a square in the picture corresponding to the omitted point at infinity.

Lemma 2 (Curtis [Cu1]) There are 132 such hexads (12 of type 1, 12 of type 2, 54 of type 3, and 54 of type 4). They form a Steiner system of type $(5,6,12)$.

The MINIMOG description

Following Curtis’ description [Cu2] of a Steiner system $S(5,8,24)$ using a $4\times 6$ array, called the MOG, Conway [Co1] found and analogous description of $S(5,6,12)$ using a $3\times 4$ array, called the MINIMOG. This section is devoted to the MINIMOG. The tetracode words are

0	0	0	0		0	+	+	+		0	-	-	-
+	0	+	-		+	+	-	0		+	-	0	+
-	0	-	+		-	+	0	-		-	-	+	0

With ”0″=0, “+”=1, “-“=2, these vectors form a linear code over GF(3). (This notation is Conway’s. One must remember here that “+”+”+”=”-“!) They may also be described as the set of all 4-tuples in of the form
$(0,a,a,a),(1,a,b,c),(2,c,b,a),$
where abc is any cyclic permutation of 012. The MINIMOG in the shuffle numbering is the array
$\begin{array}{cccc} 6 & 3 & 0 & 9\\ 5 & 2 & 7 & 10 \\ 4 & 1 & 8 & 11 \end{array}$
We label the rows of the MINIMOG array as follows:

the first row has label 0,
the second row has label +,
the third row has label –

A col (or column) is a placement of three + signs in a column of the MINIMOG array. A tet (or tetrad) is a placement of 4 + signs having entries corresponding (as explained below) to a tetracode.

+	 	 	 
 	+	+	+
 	 	 	 
0	+	+	+

+	 	 	 
 	 	 	 
 	+	+	+


0	-	-	-

 	+	 	 
+	 	+	 
 	 	 	+

+	0	+	-

 	 	 	+
+	+	 	 
 	 	+	 

+	+	-	0

 	 	+	 
+	 	 	+
 	+	 	 


+	-	0	+

 	+	 	 
 	 	 	+
+	 	+	 

-	0	-	+

 	 	+	 
 	+	 	 
+	 	 	+

-	+	0	-

 	 	 	+
 	 	+	 
+	+	 	 


-	-	+	0

Each line in $\mathbf{F}_3^2$ with finite slope occurs once in the $3\times 3$ part of some tet. The odd man out for a column is the label of the row corresponding to the non-zero digit in that column; if the column has no non-zero digit then the odd man out is a “?”. Thus the tetracode words associated in this way to these patterns are the odd men out for the tets. The signed hexads are the combinations $6$-sets obtained from the MINIMOG from patterns of the form

col-col, col+tet, tet-tet, col+col-tet.

Lemma 3 (Conway, [CS1], chapter 11, page 321) If we ignore signs, then from these signed hexads we get the 132 hexads of a Steiner system $S(5,6,12)$ . These are all possible $6$-sets in the shuffle labeling for which the odd men out form a part (in the sense that an odd man out “?” is ignored, or regarded as a “wild-card”) of a tetracode word and the column distribution is not $0,1,2,3$ in any order.

Furthermore, it is known [Co1] that the Steiner system $S(5,6,12)$ in the shuffle labeling has the following properties.

There are $11$ hexads with total $21$ and none with lower total.
The complement of any of these $11$ hexads in $\{0,1,...,11\}$ is another hexad.
There are $11$ hexads with total $45$ and none with higher total.

Mathematical blackjack

Mathematical blackjack is a 2-person combinatorial game whose rules will be described below. What is remarkable about it is that a winning strategy, discovered by Conway and Ryba [CS2] and [KR], depends on knowing how to determine hexads in the Steiner system $S(5,6,12)$ using the shuffle labeling.

Mathematical blackjack is played with 12 cards, labeled $0,\dots ,11$ (for example: king, ace, $2$ , $3$ , …, $10$ , jack, where the king is $0$ and the jack is $11$ ). Divide the 12 cards into two piles of $6$ (to be fair, this should be done randomly). Each of the $6$ cards of one of these piles are to be placed face up on the table. The remaining cards are in a stack which is shared and visible to both players. If the sum of the cards face up on the table is less than 21 then no legal move is possible so you must shuffle the cards and deal a new game. (Conway [Co2] calls such a game *={0|0}, where 0={|}; in this game the first player automatically wins.)

Players alternate moves.
A move consists of exchanging a card on the table with a lower card from the other pile.
The player whose move makes the sum of the cards on the table under 21 loses.

The winning strategy (given below) for this game is due to Conway and Ryba [CS2], [KR]. There is a Steiner system $S(5,6,12)$ of hexads in the set $\{0,1,...,11\}$ . This Steiner system is associated to the MINIMOG of in the “shuffle numbering” rather than the “modulo $11$ labeling”.

The following result is due to Ryba.

Proposition 6: For this Steiner system, the winning strategy is to choose a move which is a hexad from this system.

This result is proven in a wonderful paper J. Kahane and A. Ryba, [KR]. If you are unfortunate enough to be the first player starting with a hexad from $S(5,6,12)$ then, according to this strategy and properties of Steiner systems, there is no winning move! In a randomly dealt game there is a probability of 1/7 that the first player will be dealt such a hexad, hence a losing position. In other words, we have the following result.

Corollary 7: The probability that the first player has a win in mathematical blackjack (with a random initial deal) is 6/7.

An example game is given in this expository hexads_sage (pdf).

Bibliography

[Cu1] R. Curtis, “The Steiner system $S(5,6,12)$, the Mathieu group $M_{12}$, and the kitten,” in Computational group theory, ed. M. Atkinson, Academic Press, 1984.
[Cu2] —, “A new combinatorial approach to $M_{24}$,” Math Proc Camb Phil Soc 79(1976)25-42
[Co1] J. Conway, “Hexacode and tetracode – MINIMOG and MOG,” in Computational group theory, ed. M. Atkinson, Academic Press, 1984.
[Co2] —, On numbers and games (ONAG), Academic Press, 1976.
[CS1] J. Conway and N. Sloane, Sphere packings, Lattices and groups, 3rd ed., Springer-Verlag, 1999.
[CS2] —, “Lexicographic codes: error-correcting codes from game theory,” IEEE Trans. Infor. Theory32(1986)337-348.
[KR] J. Kahane and A. Ryba, “The hexad game,” Electronic Journal of Combinatorics, 8 (2001)

Yet Another Mathblog

Tag Archives: recreational mathematics