This is part of live presentation series called Mathematical Games in which we explore a variety of games and puzzles using Wolfram Language. In this episode, we explore the mathematical games and puzzles involving combinatorial codes and designs.

Wolfram Demonstrations Project

Many demonstrations involve Codes and Designs.

Steiner Systems (s, b, m)

s is the group size.
​b is the block size.
​m is the number of elements.
Every possible group must be a subset of one block.

S(2, 3, 7) -- The Fano Plane

In[]:=
lines=Select[Subsets[Range[7],{3}],BitXor@@#==0&]
Out[]=
{{1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,7},{3,4,7},{3,5,6}}
In[]:=
config={1,2,3,6,5,4,7};​​ResourceFunction["FindFanoPlaneIsomorphism"][config,"Diagram"][config]
Out[]=
A presentation on the Szilassi Polyhedron:
Out[]=
In[]:=
pts=CirclePoints[7];​​pick=Table[Mod[{1,2,4}+n,7,1],{n,0,6}];​​Graphics[{Table[Style[Text[k,pts[[k]]],40],{k,1,7}],{Thick,Hue[#[[1]]/7],ResourceFunction["CubicSplineCurve"][pts[[#]]]}&/@pick}]
Out[]=

S(2,3,9) : Lo Shu Magic Square

Any pair of numbers shows up in a row or column in exactly one of the grids.
In[]:=
Row[Riffle[Style[Text@Grid[Partition[#,3],Frame->All],30]&/@{Range[9],{4,9,2,3,5,7,8,1,6}}," "]]
Out[]=
1
2
3
4
5
6
7
8
9
4
9
2
3
5
7
8
1
6
Shown as triangles:
In[]:=
tri=Partition[#,3]&/@{Range[9],{4,9,2,3,5,7,8,1,6}};
Out[]=

S(2,4,16) : The 9 4 Puzzle

Fill in the second grid so that any pair of numbers shows up in a row, column or main diagonal in exactly one of the grids.
In[]:=
Row[Riffle[Style[Text@Grid[Partition[#,4],Frame->All],30]&/@{Range[16],PadRight[{9,4},16," "]}," "]]
How many pairs of numbers?
In[]:=
Length[Subsets[Range[16],{2}]]
Out[]=
120
How many pairs of numbers are represented by a row, column or main diagonal ?
In[]:=
(4+4+2)Length[Subsets[Range[4],{2}]]
Out[]=
60
To fill out the first row, there are 3 numbers to choose from. The 6 is on a diagonal.
For balance, 6 will need to be off the diagonals in the second grid.
We can fill in the first row.

Only memorize the 9 and 4

Sixteen Golfer problem:

Or we can arrange them all graphically (blue+magenta, yellow+green, orange):

S(2,5,25) : Magic Hexagon

Fill in the second grid so that any pair of numbers shows up in a row, column or wrapped \ diagonal in exactly one of the grids.
This is easier to see in a hexagonal grid:
This better presented with a clipped hexagon

S(2,7,49) :

For 7×7 grids, the grids are toroidal. In each grid the digits seen by 7 are shown.

The Marcel J. E. Golay 1949 paper. “The Best Single Page in Coding” - Berlekamp

Ternary Golay and the S(5,6,12) Steiner system

We can generate all 729 code words in the ternary Golay system:
The positions of zeros in codewords with six zeros makes the S(5,6,12) Steiner system.

Turning Turtles: Moebius and S(4,6,18)

You have 18 coins. On their turn, each player may turn over one to five coins, but their leftmost flip must be heads to tails. The last to move wins.
John Conway calls this game Moebius.
Here is a basis for generating the full code:
The following 102 codewords give S(4,6,18).

Generating the Binary Golay Code

There is a natural way to generate the binary Golay code. Just greedily find the winning positions of order 24 Turning Turtles! It’s that easy!
In the full game, you have 24 coins. On their turn, each player may turn over one to seven coins, but their leftmost flip must be heads to tails. The last to move wins.
John Conway calls this game Mogul.
It takes about five minutes to run, since 2^24 =16777216.
There is a natural way to generate the binary Golay code. Just use the inverse of the icosahedron! It’s that easy!
Just join with the identity matrix:
There is a natural way to generate the binary Golay code. Just use the mod 23 nonresidues! It’s that easy!

Repair Mission

Back in November, Voyager 1 stopped working. The 1977-era computer is a light day away, 26 billion kilometers, 16 billion miles. How do you send the new program that skips the bad processor? Remember, any signal sent that far will be corrupted. How do you overcome the corruption in a signal?
The Voyager mission uses the Golay code:
Up to three errors can be fixed in each code block.
We can try this out with
Good enough to fix Voyager.

The S(5,8,24) Steiner system

For any set of five letters from a to x, one of these 759 octads has it:

The S(4,7,23) Steiner system

For any set of four letters from a to w, one of these 253 heptads has it:

M22 Graph and the S(3,6,22) Steiner system

S(3,6,22) means that all triples are found within 6-element blocks on 22 characters. The number of blocks needed is:
We’ve punctured the code to generate smaller codes. Is it possible to go the other way?

Room Squares, Kirkman Schoolgirl Problem

Cayley solved the problem first. In White is a Room Square.
1. All possible pairs from 1-8 are given.
2. All digits 1-8 appear in each row and column.
In 1850, Cayley combined a Fano Plane and a Room Square to solve the Kirkman problem.
Note: Gino Fano (5 January 1871 – 8 November 1952).
Note: Thomas Gerald Room (10 November 1902 – 2 April 1986).

Room Sudoku

Place the 45 non-doubles from a complete double-9 set of dominos in the grid.
Every row, column and square has the digits 0-9.
The 45 dominoes make an orthogonally connected ring around the central square.
The given dominos each orthogonally touch exactly 1 or 3 other dominoes.
All hidden dominoes orthogonally touch exactly 2 dominoes in the completed grid.

Smallest Projective Space
Kirkman Schoolgirl Problem
S(2,3,15)

Generating codewords for S(2,3,15) is easy,
15 points, each on 7 planes.
15 planes, each on 7 points. {1,2,3,4,5,6,7}, {2,4,6,9,11,13,15}, {2,4,6,8,10,12,14}
Also, 35 lines each with BitXor sum 0.
If a circular wheel is used, a perfect set of measuring marks is called a difference set, a Ganymede circle, or an n-switch. All the distances between selected red points are different. The distances are indicated by arcs inside the circle.
Here are 13 parabolas, each on 4 points.
Here are 13 points, each on 4 parabolas.
From FourPointParabolas.

The Hamming(7,4) Code

by: Jacob A. Siehler
Four data bits, three parity bits.
Hamming(7,4) is a single-error correcting code that uses a 7-bit codeword to transmit four bits of data. The sender computes three parity bits for each 4-bit data word, assembles the data and parity bits into a 7-bit codeword, and transmits this codeword. The receiver computes three parity check bits from the received 7-bit word. If no error occurred in transmission, all three parity check bits will be zero. If a single bit has been changed in transmission, the value of the three parity bits (interpreted as a 3-bit binary number) will indicate the position of the error, which can then be corrected.

The 2-(64,8,1) Design

The combinatorial design 2-(64,8,1) can be represented with four squares. For any 2 integers chosen up to 64, there is exactly 1 length-8 row, column, or diagonal that contains the pair. Each square can be modified by one of the 8!! = 384 permutations that preserve rows, columns, and diagonals. Combinatorially, 2-(64,8,1) is unique.

The Set of Sets in SET

Social Golfers Problem

A group consists of 32 golfers who want to play in groups of four for several days. Can they play for ten days, with no pair of golfers in the same group twice?
In 1850, Reverend Thomas Kirkman sent a related query to the readers of a popular math magazine, Lady’s and Gentleman’s Diary: Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two will walk twice abreast. Arthur Cayley and Jakob Steiner solved the problem. For groups of three, solutions are called either a resolvable Steiner triple system (RSTS) or a Kirkman triple system (KTS).
What does the poor golf organizer do? These are incredibly difficult problems, even for mathematicians. Many are unsolved, and solutions that do exist are strangely named within math journals that are hard to obtain. The solutions often point back to earlier papers, which upon consultation end with “the construction is self-explanatory”. For 8 groups of threesomes, that explanation did not help, so a near solution with foursomes on the last day is given.

Aside: Sporadic Groups

Here are pictures of the generators:

Triangle of Optimal Binary Codes
(mouseover to see tooltips) (Perfect, Optimal, NearOptimal)

Codes with 41 > blocklength > dimension. Many from codetables.de.

CITE THIS NOTEBOOK

Mathematical Games: combinatorial codes and designs
by Ed Pegg​
Wolfram Community, STAFF PICKS, May 16, 2024
​https://community.wolfram.com/groups/-/m/t/3177778