September | 2017 | Yet Another Mathblog

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

Monthly Archives: September 2017

MINIMOGs and Mathematical blackjack