### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,270)
- misc (3)
- project euler (2)
- puzzle (67)
- site news (50)
- tantalizer (69)
- teaser (7)

### Site Stats

- 206,369 hits

Programming Enigma Puzzles

2 January 2019

Posted by on **From The Sunday Times, 10th June 2018** [link]

On holiday once with lost luggage and trapped indoors, we decided to recreate our favourite card game. With limited resources, we used just seven cards and seven images (red heart, green tree etc.) with three images on each card. Remarkably, just as in the game at home, every pair of cards had exactly one image in common. Labelling the seven images from 1 to 7, the cards were as follows:

{1,2,4} {2,3,6} {1,3,5} {1,6,7} {2,5,7} {3,4,7} {4,5,6}

Interestingly, each image appears on just three cards.

Our original set of cards at home has eight images per card, each image appears on just eight cards and again the total number of images is the same as the number of cards.

What is that number?

Today’s bonus puzzle revisits one of the *Sunday Times Teasers* from 2018 that I found interesting.

[teaser2907]

%d bloggers like this:

This comment collects together the various parts of my analysis of this puzzle in to one place. I thought this was quite an interesting puzzle — although it is straightforward to come up with the answer to the puzzle, the quest for a generic, constructive solution leads to some quite interesting maths (and programming). So here we go:

It is fairly easy to determine what the number of cards and symbols required for the answer is:

If the number of cards and the number of symbols is

n, and there areksymbols per card and each symbol appears on exactlykcards.Every pair of cards has exactly one image in common. And there are

C(n, 2)possible pairings of cards.For any particular symbol, it appears on exactly

kof the cards. Taking thesekcards we can form them intoC(k, 2)pairings of cards, and these are the only pairs that share that particular symbol.So we can list each symbol and the pairs of cards that share it, and if we do that for each of the

nsymbols we will have made a full list of all possible pairs of cards.So:

This expression simplifies to:

When

k = 8we get the required answer:Solution:There are 57 cards (and 57 symbols).Although it is straightforward to calculate the number of cards / symbols, given the required number of symbols per card, there is no guarantee that such a set of cards exists.

The puzzle gives an example for

k = 3, and claims that ak = 8example exists.When solving puzzles I like to have a constructive solution that actually demonstrates the required solution.

My first attempt was a brute force search. This worked OK to generate sets of cards for

(k = 2, n = 3),(k = 3, n = 7),(k = 4, n = 13),(k = 5, n = 21), and even(k = 6, n = 31). Although that last one took nearly 3 hours to calculate, so it was clear I wasn’t going to get further using this approach.It turns out that for

ksymbols, we can construct a set of cards if there is afinite projective planeof order(k – 1). (See: [ Wikipedia ]).A finite projective plane of order

Nconsists of(N² + N + 1)points and(N² + N + 1)lines. Where there are exactly(N + 1)points on each line, and each line passes through exactly(N + 1)points.So if we assign a symbol to each point, then each of the

(N + 1)lines defines a card with(N + 1)symbols on it, with the required properties. Alternatively, we could assign a symbol to each line, and then each point defines a card with the(N + 1)symbols given by the lines that pass through that point.It is not known for certain exactly which orders of finite projective planes are possible to construct, but if

N = p^n, for some primepand some positive integern, then theGalois Fieldof orderN— denotedGF(N)— provides a finite projective plane. And allknownfinite projective planes can be constructed in this way.There is a theorem that for a finite projective plane to exist of order

NwhereN mod 4is 1 or 2, thenNmust be the sum of two squares (although this doesn’t show that a projective plane will exist if the condition holds, only that it won’t exist if the condition doesn’t hold). (See: [ Wikipedia ]). In particular this means there cannot be a projective plane of order 6. (So there is no set of cards with 7 symbols per card).And even though 10 is the sum of two squares (10 = 1² + 3²) the existence of a projective plane of order 10 has been shown to be impossible by extensive computer search (see: [ PDF ]). (So there is no set of cards with 11 symbols per card). It is not known if a projective plane of order 12 exists (although it is thought that it doesn’t).

The upshot of all this is, that we can construct projective planes of order

N = p^n. Other orders probably don’t exist, and if they do, we are unlikely to find them with a simple Python program.So, if we construct projective planes of order, 2, 3, 4, 5, 7, 8, 9, 11, (which we can do by generating the appropriate Galois Field) then we can use these to make sets of cards with 3, 4, 5, 6, 8, 9, 10, 12 symbols, and the corresponding numbers of cards are: 7, 13, 21, 31, 57, 73, 91, 133.

In summary:

I wrote code to generate Galois Fields in

galois.py(details below), and then used that to allow the generation of sets of cards appropriate for the puzzle. The program then verifies that the set of cards generated satisfy the conditions. (It takes longer to do the verification than it does to generate the set of cards in the first place).This Python 3 program runs in 83ms:

Run:[ @repl.it ]So, how do we implement Galois Fields

GF(N), whereN = p^n, I hear you ask?Some fields are easier to implement than others.

For a start if

n = 1(i.e.Nis a prime) then taking the integers moduloN, with the standard addition and multiplication operations (also moduloN), provides us with an implementation ofGF(N).This is easily implemented by the [[

_GF_mod()]] class ingalois.py.To construct a set of cards that gives an answer to the puzzle we only need to consider

k = 8, which means we are looking for the Galois FieldGF(7), and 7 is a prime, so this is enough to demonstrate that there is an answer to the puzzle. (And works for sets of 3, 4, 6, 12 cards, etc.). But I wanted a generic solution, so I carried on…If

n > 1the construction is more complicated:Instead of integers we use polynomials (of degree less than

nover the fieldsGF(p)). The operations are done moduloR, whereRis anirreducible polynomialof degreenoverGF(p). Irreducible polynomials behave a bit like primes in the integers. (See: [ Wikipedia ]).In the case of

GF(2^n)the operations are fairly easily implemented using binary arithmetic (see the [[_GF_2()]] class ingalois.py), providing you have the irreducible polynomial available. In the code I provide irreducible polynomials up ton = 11, so we can easily do powers of 2 up to 2048 (and if you happen to know an appropriate irreducible polynomial for higher powers you can provide it). This lets us find sets of cards with size 5, 9, 17, etc.Using the various [[

poly_*()]] functions fromenigma.pyalong with a couple extra polynomial routines we can implement the polynomial case for generalGF(p^n). Again this is all fine, providing we have an appropriate irreducible polynomial. In the code I provided enough irreducible polynomials for all possibleNup to 2000 (which lets you generate sets of cards that take far too long to verify).But what happens when want to make a field that we don’t have an irreducible polynomial for?

Actually quite a lot of the polynomials in a field are irreducible, so we can just pick a polynomial and then test it to see if it’s irreducible. If not we try another one. The fact that quite a lot of the polynomials in the field are irreducible means we won’t have to try too many. The test for irreducibility that I implemented in

galois.pyis given here: [ Wikipedia ].So at this point we have code that can construct any viable Galois Field.

The code for

galois.pyis available onGitHub[ link ].