Kittens, $S(5,6,12)$, and Mathematical blackjack in SAGE

David Joyner1 and Ann Casey

5-21-2006

Abstract:

This is an exposition of some ideas of Conway, Curtis, and Ryba on $S(5,6,12)$ and a card game called mathematical blackjack. An implementation in Python is described as well.


Contents

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,...,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.

This note focuses on $S(5,6,12)$. If $S$ is a Steiner system of type $(5,6,12)$ in a $12$-set $X$ then the symmetric group $S_X$ 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 S_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=\{1,2,...,12\}$ then any two such groups, for different Steiner systems in $X$, must be conjugate in $S_X$. In particular, such a definition is well-defined up to isomorphism.)

Curtis' kitten, Conway's minimog

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

\begin{displaymath} \mathbf{P}^1(\mathbf{F}_{11}) =\{\infty,0,1,2,...,9,10\} \end{displaymath}

denote the projective line over the finite field $\mathbf{F}_{11}$ with $11$ elements. Let

\begin{displaymath} Q=\{0,1,3,4,5,9\} \end{displaymath}

denote the quadratic residues and $0$ and let

\begin{displaymath} L = \langle \alpha,\beta \rangle \cong PSL(2,\mathbf{F}_{11}), \end{displaymath}

where $\alpha(y)=y+1$ and $\beta(y)=-1/y$. Let

\begin{displaymath} S=\{\lambda(Q) \vert \lambda\in L\}. \end{displaymath}

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'').

          $\infty$          
                     
          6          
                     
        2   10        
                     
      5   7   3      
                     
    6   9   4   6    
                     
  2   10   8   2   10  
                     
0                   1
                     

Curtis' Kitten.

The ``views'' from each of the three ``points at infinity'' ( $\{0,1,\infty\}$ are the ``points at infinity'' in the ``modulo 11 labeling) is given in the following tables.

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

5 7 3
9 4 6
8 2 10
picture at $\infty$ picture at $0$ picture at $1$

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.

$\bullet$ $\bullet$ $\bullet$
$\times$ $\times$ $\times$
$\circ$ $\circ$ $\circ$
$\bullet$ $\times$ $\circ$
$\bullet$ $\times$ $\circ$
$\bullet$ $\times$ $\circ$
$\bullet$ $\times$ $\circ$
$\circ$ $\bullet$ $\times$
$\times$ $\circ$ $\bullet$
$\times$ $\circ$ $\bullet$
$\circ$ $\bullet$ $\times$
$\bullet$ $\times$ $\circ$
slope 0 slope infinity slope -1 slope 1

The union of any two perpendicular lines is called a cross. There are 18 crosses. The crosses of this plane are described by one of the following patterns of filled circles.

$\bullet$ $\bullet$ $\bullet$
$\bullet$ $\circ$ $\circ$
$\bullet$ $\circ$ $\circ$
$\bullet$ $\circ$ $\circ$
$\bullet$ $\bullet$ $\bullet$
$\bullet$ $\circ$ $\circ$
$\bullet$ $\circ$ $\circ$
$\bullet$ $\circ$ $\circ$
$\bullet$ $\bullet$ $\bullet$

$\bullet$ $\bullet$ $\bullet$
$\circ$ $\bullet$ $\circ$
$\circ$ $\bullet$ $\circ$
$\bullet$ $\bullet$ $\bullet$
$\circ$ $\circ$ $\bullet$
$\circ$ $\circ$ $\bullet$
$\circ$ $\bullet$ $\circ$
$\bullet$ $\bullet$ $\bullet$
$\circ$ $\bullet$ $\circ$

$\circ$ $\circ$ $\bullet$
$\bullet$ $\bullet$ $\bullet$
$\circ$ $\circ$ $\bullet$
$\circ$ $\circ$ $\bullet$
$\circ$ $\circ$ $\bullet$
$\bullet$ $\bullet$ $\bullet$
$\circ$ $\bullet$ $\circ$
$\circ$ $\bullet$ $\circ$
$\bullet$ $\bullet$ $\bullet$

$\bullet$ $\circ$ $\bullet$
$\circ$ $\bullet$ $\circ$
$\bullet$ $\circ$ $\bullet$
$\circ$ $\bullet$ $\bullet$
$\circ$ $\bullet$ $\bullet$
$\bullet$ $\circ$ $\circ$
$\circ$ $\circ$ $\bullet$
$\bullet$ $\bullet$ $\circ$
$\bullet$ $\bullet$ $\circ$

$\bullet$ $\bullet$ $\circ$
$\bullet$ $\bullet$ $\circ$
$\circ$ $\circ$ $\bullet$
$\bullet$ $\circ$ $\circ$
$\circ$ $\bullet$ $\bullet$
$\circ$ $\bullet$ $\bullet$
$\circ$ $\bullet$ $\bullet$
$\bullet$ $\circ$ $\circ$
$\circ$ $\bullet$ $\bullet$

$\circ$ $\bullet$ $\circ$
$\bullet$ $\circ$ $\bullet$
$\bullet$ $\circ$ $\bullet$
$\bullet$ $\bullet$ $\circ$
$\circ$ $\circ$ $\bullet$
$\bullet$ $\bullet$ $\circ$
$\bullet$ $\circ$ $\bullet$
$\bullet$ $\circ$ $\bullet$
$\circ$ $\bullet$ $\circ$

The complement of a cross in $\mathbf{F}_3^2$ is called a square. Of course there are also 18 squares and the squares of this plane are described by one of the above patterns of hollow circles.

The hexads are

  1. three ``points at infinity'' union any line,

  2. the union of any two (distinct) parallel lines in the same picture,
  3. one ``point at infinity'' union a cross in the corresponding picture,
  4. 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 $\mathbf{F}_3$. (This notation is Conway's. One must remember here that ``+''+``+''=``-'' and ``-''+``-''=``+''!) They may also be described as the set of all 4-tuples in $\mathbf{F}_3$ of the form

\begin{displaymath} (0,a,a,a), (1,a,b,c), (2,c,b,a), \end{displaymath}

where $abc$ is any cyclic permutation of $012$.

The MINIMOG in the shuffle labeling is the $3\times 4$ array

\begin{displaymath} \begin{array}{cccc} 6 & 3 & 0 & 9\\ 5 & 2 & 7 & 10 \\ 4 & 1 & 8 & 11 \end{array}\end{displaymath}

(For comparison, the MINIMOG in the modulo 11 labeling is given in 1.2 below. We shall use the shuffle labeling below unless stated otherwise.)

We label the rows as follows:

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

A col (or column) is a placement of three + signs in a column of the array:

+      
+      
+      
  +    
  +    
  +    
    +  
    +  
    +  
      +
      +
      +

A tet (or tetrad) is a placement of 4 ``+'' signs in the $3\times 4$ array having entries corresponding to a tetracode as follows:

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

Each line in $\mathbf{F}_3^2$ with finite slope occurs once in the rightmost $3\times 3$ block 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 2.

Example 4   Associated to the col-col pattern
+
+
+
-
+
+
+
=
+ -
+ -
+ -
is the tetracode $0 0 ? ?$ and the signed hexad $\{-1,-2,-3,4,5,6\}$ and the hexad $\{1,2,3,4,5,6\}$.

Indeed, you can see this in SAGE (after loading hexad.sage) as follows: 

sage: minimog_shuffle

[ 6  3  0  9]
[ 5  2  7 10]
[ 4  1  8 11]
sage: col[0]-col[1]

[1 2 0 0]
[1 2 0 0]
[1 2 0 0]
To verify this, you can see that: 

sage: find_hexad([1,2,3,4,5],minimog_shuffle)
      ([1, 2, 3, 4, 5, 6], ['square 8', 'picture 0'])

Associated to the col+tet pattern

+
+
+
-
+
+ + +
=
+ +
- + +
+
is the tetracode $0 + + +$ and the signed hexad $\{1,-2,3,6,7,10\}$ and the hexad $\{1,2,3,6,7,10\}$.

Likewise, you can check this in SAGE using the commands: 

sage: col[1]-tet[1]

[2 1 0 0]
[0 0 2 2]
[0 1 0 0]
sage: find_hexad([1,2,3,6,7],minimog_shuffle)
      ([1, 2, 3, 6, 7, 10], ['square 5', 'picture 0'])

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


The shuffle kitten

The MINIMOG in the shuffle numbering is the $3\times 4$ array

\begin{displaymath} \begin{array}{cccc} 6 & 3 & 0 & 9\\ 5 & 2 & 7 & 10 \\ 4 & 1 & 8 & 11 \end{array}\end{displaymath}

minimog-shuffle

Since Steiner systems $S(5,6,12)$ are unique up to relabelings, we should expect a ``kitten'' for the shuffle labeling. There is one and this section describes it.

In Conway, [Co1], the MINIMOG for the ``modulo 11 labeling'' is given:

\begin{displaymath} \begin{array}{cccc} 0 & 3 & \infty & 2\\ 5 & 9 & 8 & 10 \\ 4 & 1 & 6 & 7 \end{array}\end{displaymath}

Comparing this MINIMOG with that for the shuffle labeling, we obtain the following kitten.

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

The Shuffle Kitten.

The ``views'' from each of the three ``points at infinity'' is given in the following tables.

5 11 3
8 2 4
9 10 7
5 11 3
2 4 8
7 9 10

8 10 3
9 11 4
5 2 7
picture at $6$ picture at $1$ picture at $0$

Example 5  

SAGE examples

First, you need the file hexad.sage and the CAS SAGE, which can be downloaded and saved to your computer. When you start SAGE, you'll see a banner and command-line prompt something like this: 

--------------------------------------------------------------
| SAGE Version x.y.z, Build Date: yyyy-mm-dd                  |
| Type notebook() for the GUI, and license() for information. |
--------------------------------------------------------------

sage:
If you save this file in the directory spam,say, then in SAGE, the command 
         sage: attach 'spam/hexad.sage'
at the command line will load the file. (If desired, you can either read the code documentation in the file for examples or type find_hexad? or blackjack_move? for command-line details, though most are already in the pdf version of this paper.) Here are some examples of SAGE input and output: 

        sage: find_hexad([0,1,2,3,4],minimog_shuffle)
        ([0, 1, 2, 3, 4, 11], ['square 2', 'picture 6'])
        sage: find_hexad([1,2,3,4,5],minimog_shuffle)
        ([1, 2, 3, 4, 5, 6], ['square 8', 'picture 0'])
        sage: find_hexad([2,3,4,5,8],minimog_shuffle)
        ([2, 3, 4, 5, 8, 11], ['lines (1, 2)', 'picture 1'])
        sage: find_hexad([0,1,2,4,6],minimog_shuffle)
        ([0, 1, 2, 4, 6, 8], ['line 1', 'picture 1'])

The first example (find_hexad([0,1,2,3,4],minimog_shuffle)) asks SAGE to find the hexad in $S(5,6,12)$ containing $\{0,1,2,3,4\}$ in the shuffle labeling (SAGE knows minimog_shuffle is the $3\times 4$ minimog matrix above - you don't have to enter that.). SAGE says that it is a square in the picture at the ``point at infinity'' $6$ (the numbering of the squares is made explicit in the file but does not correspond with the order they are presented above).

Indeed, the picture at the ``point at infinity'' $6$ is

5 11 3
8 2 4
9 10 7
and the square referred to is
$\bullet$ $\circ$ $\circ$
$\bullet$ $\circ$ $\circ$
$\bullet$ $\bullet$ $\bullet$
You can see that these correspond to the hexad $[0,1,2,3,4,11]$ using Curtis' Lemma above.

The other examples are similar and we ask that the interested reader check them as an exercise.

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.

Winning ways in mathematical blackjack

Mathematical blackjack is played with 12 cards, labeled $0,...,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 or equal to 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=\{\vert\}$; in this game the first player automatically loses and so you courteously offered the first move!.)

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''.

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

This result is proven in [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

\begin{displaymath} {132\over{\left( \begin{array}{c} 12 \ 6\end{array}\right)}} =1/7 \end{displaymath}

that the first player will be dealt such a hexad, hence a losing position. In other words, we have the following result.

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

Example 8  

Example 9   Actually, SAGE would play this game another way (also leading to a win). 

        sage: blackjack_move([0,2,4,6,7,11],minimog_shuffle)
        '4 --> 3. The total went from 30 to 29.'
Is this really a hexad? 

        sage: find_hexad([11,2,3,6,7],minimog_shuffle)
        ([0, 2, 3, 6, 7, 11], ['square 9', 'picture 1'])
        sage: blackjack_move([0,2,3,6,7,11],minimog_shuffle)
        This is a hexad.
        There is no winning move, so make a random legal move.
        [0, 2, 3, 6, 7, 11]
Yes, SAGE tells you that it is indeed a hexad.

Suppose player 2 replaced the 11 by a 9. Your next move: 

        sage: blackjack_move([0,2,3,6,7,9],minimog_shuffle)
        '7 --> 1. The total went from 27 to 21.'
You have now won. SAGE will even tell you so: 
        sage: blackjack_move([0,2,3,6,1,9],minimog_shuffle)
        'No move possible. Shuffle the deck and redeal.'

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)

[S] SAGE: Software for Algebra and Geometry Experimentation
http://modular.math.washington.edu/sage/
http://sage.scipy.org/sage/
http://sage.sf.net/

About this document ...

Kittens, $S(5,6,12)$, and Mathematical blackjack in SAGE

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -t 'Kittens, blackjack, and SAGE' -split 0 hexads_sage.tex

The translation was initiated by wdj on 2006-05-21

Footnotes

... Joyner1
Math Dept, USNA, wdj@usna.edu. I thank Alex Ryba and Andy Buchanan for helpful comments and corrections to a paper written with my former student Ann Luers (now Ann Casey) in 1997. It has been corrected and rewritten by the first author in 2006, with some examples using the computer algebra system SAGE.
... order2
That is to say, the following cannot occur: some column has 0 entries, some column has exactly 1 entry, some column has exactly 2 entries, and some some column has exactly 3 entries.
wdj 2006-05-21