The MDS Conjecture

I will begin with a couple of games you can play with the ternary [4,2]-Hamming code, in much the same way Peter Cameron describes here and in a previous post of mine for a different Hamming code.

Choose a number between 0 and 8 (inclusive). I will ask you four questions, you can answer ‘a’, ‘b’ or ‘c’ and you are allowed to lie at most once. Here are my questions:

  1. Is your number (a) less than 3 (b) between 3 and 5 (c) more than 5?
  2. Is your number (a) 0 mod 3 (b) 1 mod 3 (c) 2 mod 3?
  3. Is your number in (a) {0,5,7} (b) {1,3,8} or (c) {2,4,6}?
  4. Is your numberin (a) {0,4,8} (b) {1,5,6} or (c) {2,3,7}?

From these questions, I can easily determine your number.

Continue reading “The MDS Conjecture”

Appreciating the Hamming [7,4,3]-code

You might be familiar with Richard Ehrenborg’s beautiful game where your friend chooses a number from 0 to 15, and you proceed to show in turn seven cards, asking which side of the card the number is on, and then placing each card down carefully on a base card. Each card has a funny shape, with squares poking out at the edges.

The Base Card
Is your number on this side?

Your friend can lie at most once, and so once the cards have been placed down, the number on the base card which is covered at most once by a protruding square, is the number your friend has chosen. What is so cool about this trick is that you have an excellent information rate — seven questions, sixteen numbers to choose from and one lie. What makes this tick is a perfect code, which was known earlier by Golay but is attributed to Hamming (as he could publish his findings and Golay could not). (See Chapter 1, Section 6 of Thomas Thompson’s book). This code has code length 7, dimension 4 and minimum distance 3. So it can correct single errors and detect two errors. However, in demonstrating the glory of the Hamming code to the uninitiated, I felt something was missing; a crappier precursor.

I’ve come up with a simpler game based on a [6,3,3]-code which has a (poor)  information rate of  0.5, and is certainly not perfect (the Hamming bound here is 64/7). The generator matrix for this linear code is

\begin{bmatrix}1&0&0&0&1&1\\ 0&1&0&1&0&1\\ 0&0&1&1&1&0\end{bmatrix}.

Your friend chooses a number from 0 to 7, and you proceed to present six cards in turn, asking which side of the card the number is on, and then placing each card down carefully on a base card. It still works like the Hamming code, but makes the Hamming code look so much better in comparison. The cards are attached.

The Six Cards

Is there a 16-clue Sudoku puzzle?

A few years ago, when the Sudoku craze briefly swept the world, I became interested in one particular mathematical aspect of Sudoku – namely, what is the minimum number of clues needed for a puzzle that can be uniquely completed.

This is actually just one instance of a whole family of combinatorial problems, usually studied under names such as defining sets or critical sets, that considers when a combinatorial structure (such as a Latin square) can be reconstructed uniquely from a (small) portion of the structure.

Around that time, I found an obscure Japanese website (whose identity I have long forgotten) that had a couple of uniquely-completable Sudoku puzzles with only 17 clues. (As I am only interested in uniquely completable puzzles, I’ll drop the adjectives from now on and just assume that “puzzle” always means “uniquely completable puzzle”.)  I took these puzzles and started to “perturb” them in various ways, perhaps by swapping a number for another number, or shifting an entry to another cell, all the time keeping track of any new ones that I found. I was hoping that by finding enough 17-clue puzzles, I would eventually stumble across a 16-clue puzzle contained in one of the 17-clue ones. Continue reading “Is there a 16-clue Sudoku puzzle?”

Up ↑