puzzle – Page 6 – neverendingbooks

mini-sudokube

Published December 29, 2007 by lieven

Via the Arcadian functor I learned of the existence of the Sudokube (picture on the left).

Sudokube is a variation on a Rubik’s Cube in which each face resembles one-ninth of a Sudoku grid: the numbers from one to nine. This makes solving the cube slightly more difficult than a conventional Rubik’s Cube because each number must be in the right place and the centre cubies must also be in the correct orientation.

A much more interesting Sudoku-variation of the cube was invented two weeks ago by one of my freshmen-grouptheory students and was dubbed the mini-sudokube by him. Here’s the story.

At the end of my grouptheory course I let the students write a paper to check whether they have research potential. This year the assignment was to read through the paper mini-sudokus and groups by Carlos Arcos, Gary Brookfield and Mike Krebs, and do something original with it.

Mini-Sudoku is the baby $2 \times 2 $ version of Sudoku. Below a trivial problem and its solution

Of course most of them took the safe road and explained in more detail a result of the paper. Two of them were more original. One used the mini-sudoku solutions to find solutions for 4×4 sudokus, but the most original contribution came from Ibrahim Belkadi who wanted to count all mini-sudokubes. A mini-sudokube is a cube with a mini-sudoku solution on all 6 of its sides BUT NUMBERS CARRY OVER CUBE-EDGES. That is, if we have as the mini-sudoku given by the central square below on the top-face of the cube, then on the 4 side-faces we have already one row filled in.

The problem then is to find out how many compatible solutions there are. It is pretty easy to see that top- and bottom-faces determine all squares of the cube, but clearly not all choices are permitted. For example, with the above top-face fixed there are exactly 4 solutions. Let ${ a,b } = { 1,4 } $ and ${ c,d } = { 2,3 } $ then these four solutions are given below

Putting one of these solutions (or any other) on a $4 \times 4 $-Rubik cube would make a more interesting puzzle, I think. I’ve excused Ibrahim from having to take examination on condition that he writes down what he can prove on his mini-sudokubes by that time. Looking forward to it!

The M(13)-groupoid (2)

Published July 30, 2007 by lieven

Conway’s puzzle M(13) involves the 13 points and 13 lines of $\mathbb{P}^2(\mathbb{F}_3) $. On all but one point numbered counters are placed holding the numbers 1,…,12 and a move involves interchanging one counter and the ‘hole’ (the unique point having no counter) and interchanging the counters on the two other points of the line determined by the first two points. In the picture on the left, the lines are respresented by dashes around the circle in between two counters and the points lying on this line are those that connect to the dash either via a direct line or directly via the circle. In the first part we saw that the group of all reachable positions in Conway’s M(13) puzzle having the hole at the top positions contains the sporadic simple Mathieu group $M_{12} $ as a subgroup. To see the reverse inclusion we have to recall the definition of the ternary Golay code named in honour of the Swiss engineer Marcel Golay who discovered in 1949 the binary Golay code that we will encounter _later on_.

The ternary Golay code $\mathcal{C}_{12} $ is a six-dimenional subspace in $\mathbb{F}_3^{\oplus 12} $ and is spanned by its codewords of weight six (the Hamming distance of $\mathcal{C}_{12} $ whence it is a two-error correcting code). There are $264 = 2 \times 132 $ weight six codewords and they can be obtained from the 132 hexads, we encountered before as the winning positions of Mathieu’s blackjack, by replacing the stars by signs + or – using the following rules. By a tet (from tetracodeword) we mean a 3×4 array having 4 +-signs indicating the row-positions of a tetracodeword. For example

$~\begin{array}{|c|ccc|} \hline & + & & \\ + & & + & \\ & & & + \\ \hline + & 0 & + & – \end{array} $ is the tet corresponding to the bottom-tetracodeword. $\begin{array}{|c|ccc|} \hline & + & & \\ & + & & \\ & + & & \\ \hline & & & \end{array} $ A col is an array having +-signs along one of the four columns. The signed hexads will now be the hexads that can be written as $\mathbb{F}_3 $ vectors as (depending on the column-distributions of the stars in the hexad indicated between brackets)

$col-col~(3^20^2)\qquad \pm(col+tet)~(31^3) \qquad tet-tet~(2^30) \qquad \pm(col+col-tet)~(2^21^2) $

For example, the hexad on the right has column-distribution $2^30 $ so its signed versions are of the form tet-tet. The two tetracodewords must have the same digit (-) at place four (so that they cancel and leave an empty column). It is then easy to determine these two tetracodewords giving the signed hexad (together with its negative, obtained by replacing the order of the two codewords)

$\begin{array}{|c|ccc|} \hline \ast & \ast & & \\ \ast & & \ast & \\ & \ast & \ast & \\ \hline – & + & 0 & – \end{array} $ signed as
$\begin{array}{|c|ccc|} \hline + & & & \\ & & & \\ & + & + & + \\ \hline 0 & – & – & – \end{array} – \begin{array}{|c|ccc|} \hline & + & & \\ + & & + & \\ & & & + \\ \hline + & 0 & + & – \end{array} = \begin{array}{|c|ccc|} \hline + & – & & \\ – & & – & \\ & + & + & \\ \hline – & + & 0 & – \end{array} $

and similarly for the other cases. As Conway&Sloane remark ‘This is one of many cases when the process is easier performed than described’.

We have an order two operation mapping a signed hexad to its negative and as these codewords span the Golay code, this determines an order two automorphism of $\mathcal{C}_{12} $. Further, forgetting about signs, we get the Steiner-system S(5,6,12) of hexads for which the automorphism group is $M_{12} $ hence the automorphism group op the ternary Golay code is $2.M_{12} $, the unique nonsplit central extension of $M_{12} $.

Right, but what is the connection between the Golay code and Conway’s M(13)-puzzle which is played with points and lines in the projective plane $\mathbb{P}^2(\mathbb{F}_3) $? There are 13 points $\mathcal{P} $ so let us consider a 13-dimensional vectorspace $X=\mathbb{F}_3^{\oplus 13} $ with basis $x_p~:~p \in \mathcal{P} $. That is a vector in X is of the form $\vec{v}=\sum_p v_px_p $ and consider the ‘usual’ scalar product $\vec{v}.\vec{w} = \sum_p v_pw_p $ on X. Next, we bring in the lines in $\mathbb{P}^2(\mathbb{F}_3) $.

For each of the 13 lines l consider the vector $\vec{l} = \sum_{p \in l} x_p $ with support the four points lying on l and let $\mathcal{C} $ be the subspace (code) of X spanned by the thirteen vectors $\vec{l} $. Vectors $\vec{c},\vec{d} \in \mathcal{C} $ satisfy the remarkable identity $\vec{c}.\vec{d} = (\sum_p c_p)(\sum_p d_p) $. Indeed, both sides are bilinear in $\vec{c},\vec{d} $ so it suffices to check teh identity for two line-vectors $\vec{l},\vec{m} $. The right hand side is then 4.4=16=1 mod 3 which equals the left hand side as two lines either intersect in one point or are equal (and hence have 4 points in common). The identity applied to $\vec{c}=\vec{d} $ gives us (note that the squares in $\mathbb{F}_3 $ are {0,1}) information about the weight (that is, the number of non-zero digits) of codewords in $\mathcal{C} $

$wt(\vec{c})~mod(3) = \sum_p c_p^2 = (\sum_p c_p)^2 \in \{ 0,1 \} $

Let $\mathcal{C}’ $ be the collection of $\vec{c} \in \mathcal{C} $ of weight zero (modulo 3) then one can verify that $\mathcal{C}’ $ is the orthogonal complement of $\mathcal{C} $ with respect to the scalar product and that the dimension of $\mathcal{C} $ is seven whereas that of $\mathcal{C}’ $ is six.
Now, let for a point p be $\mathcal{G}_p $ the restriction of

$\mathcal{C}_p = \{ c \in \mathcal{C}~|~c_p = – \sum_{q \in \mathcal{P}} c_q \} $

to the coordinates of $\mathcal{P} – \{ p \} $, then $\mathcal{G}_p $ is clearly a six dimensional code in a 12-dimensional space. A bit more work shows that $\mathcal{G}_p $ is a self-dual code with minimal weight greater or equal to six, whence it must be the ternary Golay code! Now we are nearly done. _Next time_ we will introduce a reversi-version of M(13) and use the above facts to deduce that the basic group of the Mathieu-groupoid indeed is the sporadic simple group $M_{12} $.

References

Robert L. Griess, “Twelve sporadic groups” chp. 7 ‘The ternary Golay code and $2.M_{12} $’

John H. Conway and N. J.A. Sloane, “Sphere packings, lattices and groups” chp 11 ‘The Golay codes and the Mathieu groups’

John H. Conway, Noam D. Elkies and Jeremy L. Martin, ‘The Mathieu group $M_{12} $ and its pseudogroup extension $M_{13} $’ arXiv:math.GR/0508630

Mathieu’s blackjack (1)

Published July 16, 2007 by lieven

Mathieu’s blackjack is a two-person combinatorial game played with 12 cards of values 0,1,2,…,11. For example take from any deck the numbered cards together with the jack (value 11) and the queen (value 0) (btw. if you find this PI by all means replace the queen by a zero-valued king). Shuffle the cards and divide them into two piles of 6 cards (all of them face up on the table) : the main-pile and the other-pile. The rules of the game are

players alternate moves
a move consists of exchanging a card of the main-pile with a lower-valued card from the other-pile
the player whose move makes the sum of all cards in the main-pile under 21 looses the game

For example, the starting main-pile might consist of the six cards

This pile has total value 3+4+7+8+9+11=42. A move replaces one of these cards with a lowever vlued one not in the pile. So for example, replacing 8 with 5 or 1 or 2 or the queen are all valid moves. A winning move from this situation is for example replacing 8 by the queen (value 0) decreasing the value from 42 to 34

But there are otthers, such as replacing 11 by 5, 9 by 1 or 4 by 2. To win this game you need to know the secrets of the tetracode and the MINIMOG.

The tetracode is a one-error correcting code consisting of the following nine words of length four over $\mathbb{F}_3 = { 0,+,- } $

$~\begin{matrix} 0~0 0 0 & 0~+ + + & 0~- – – \\ +~0 + – & +~+ – 0 & +~- 0 + \\ -~0 – + & -~+ 0 – & -~- + 0 \end{matrix} $

The first element (which is slightly offset from the rest) is the slope s of the words, and the other three digits cyclically increase by s (in the field $\mathbb{F}_3 $). Because the Hamming-distance is 3 (the minimal number of different digits between two codewords), the tetracode can correct one error, meaning that if at most one of the four digits gets distorted by the channel one can detect and correct this. For example, if you would receive the word $+~++- $ (which is not a codeword) and if you would know that at most one digits went wrong, you can deduce that the word $+~0+- $ was sent. Thus, one can solve the 4-problem for the tetracode : correctt a tetracodeword given all 4 of its digits, one of which may be mistaken.

Another easy puzzle is the 2-problem for the tertracode : complete a tetracodeword from any 2 of its digits. For example, given the incomplete word $?~?0+ $ you can decide that the slope should be + and hence that the complete word must be $+~-0+ $.

We will use the MINIMOG here as a way to record the blackjack-position. It is a $4 \times 3 $ array where the 12 boxes correspond to the card-values by the following scheme

$\begin{array}{|c|ccc|} \hline 6 & 3 & 0 & 9 \\ 5 & 2 & 7 & 10 \\ 4 & 1 & 8 & 11 \\ \hline \end{array} $

and given a blackjack-position we place a star in the corresponding box, so the above start-position (resp. after the first move) corresponds to

$~\begin{array}{|c|ccc|} \hline & \ast & & \ast \\ & & \ast & \\ \ast & & \ast & \ast \\ \hline – & 0 & 0 & + \end{array}~ $ respectively $\begin{array}{|c|ccc|} \hline & \ast & \ast & \ast \\ & & \ast & \\ \ast & & & \ast \\ \hline – & 0 & – & + \end{array} $

In the final row we have added elements of $\mathbb{F}_3 $ indicating wher ethe stars are placed in that column (if there is just one star, we write the row-number of the star (ordered 0,+,- from top to bottom), if there are two stars we record the row-number of the empty spot. If we would have three or no stars in a column we would record a wild-card character : ?

Observe that the final row of the start position is $-~00+ $ which is NOT a tetracodeword, whereas that of the winning position $-~0-+ $ IS a tetracodeword! This is the essence of the _Conway-Ryba winning strategy_ for Mathieu’s blackjack. There are precisely 132 winning positions forming the Steiner-system S(5,6,12). By an S(5,6,12) we mean a collection of 6-element subsets (our card-piles) from a 12-element set (the deck minus the king) having the amazing property that for EVERY 5-tuple from the 12-set there is a UNIQUE 6-element set containing this 5-tuple. Hence, there are exactly $\begin{pmatrix} 12 \\\ 5 \end{pmatrix}/6 = 132 $ elements in a Steiner S(5,6,12) system. The winning positions are exactly those MINOMOGs having 6 stars such that the final row is a tetracodeword (or can be extended to a tetracodeword replacing the wildcards ? by suitable digits) and such that the distribution of the stars over the columns is NOT (3,2,1,0) in any order.

Provided the given blackjack-position is not in this Steiner-system (and there is only a 1/7 chance that it is), the strategy is clear : remove one of the stars to get a 5-tuple and determine the unique 6-set of the Steiner-system containing this 5-tuple. If the required extra star corresponds to a value less than the removed star you have a legal and winning move (if not, repeat this for another star). Finding these winning positions means solving 2- and 4-problems for the tetracode. _Another time_ we will say more about this Steiner system and indicate the relation with the Mathieu group $M_{12} $.

References

J.H. Conway and N.J.A. Sloane, ‘The Golay codes and the Mathieu groups’, chp. 10 of “Sphere Packings, Lattices and Groups“

David Joyner and Ann Casey-Luers, ‘Kittens, S(5,6,12) and Mathematical blackjack in SAGE‘

Tag: puzzle

mini-sudokube

The M(13)-groupoid (2)

Mathieu’s blackjack (1)