Enigmatic Code

Programming Enigma Puzzles

Teaser 2907: Combinatorial cards

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]

One response to “Teaser 2907: Combinatorial cards

  1. Jim Randell 2 January 2019 at 8:49 am

    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 are k symbols per card and each symbol appears on exactly k cards.

    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 k of the cards. Taking these k cards we can form them into C(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 n symbols we will have made a full list of all possible pairs of cards.

    So:

    n.C(k, 2) = C(n, 2)

    This expression simplifies to:

    n = k(k – 1) + 1 = k² – k + 1

    When k = 8 we get the required answer:

    from enigma import C, printf
    
    for k in [3, 8]:
      n = k * (k - 1) + 1
      assert C(n, 2) == n * C(k, 2)
      printf("{k} symbols per card -> {n} cards")
    

    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 a k = 8 example 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 k symbols, we can construct a set of cards if there is a finite projective plane of order (k – 1). (See: [ Wikipedia ]).

    A finite projective plane of order N consists 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 prime p and some positive integer n, then the Galois Field of order N — denoted GF(N) — provides a finite projective plane. And all known finite projective planes can be constructed in this way.

    There is a theorem that for a finite projective plane to exist of order N where N mod 4 is 1 or 2, then N must 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:

     k    n   N   field
     3    7   2   GF(2)
     4   13   3   GF(3)
     5   21   4   GF(2^2)
     6   31   5   GF(5)
     7   43   6   [impossible]
     8   57   7   GF(7)
     9   73   8   GF(2^3)
    10   91   9   GF(3^2)
    11  111  10   [impossible]
    12  133  11   GF(11)
    13  157  12   [probably impossible]

    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 ]

    from itertools import product, combinations
    from enigma import arg, is_square, isqrt, prime_factor, irange, Accumulator, printf
    
    # can we make a projective plane of order N ?
    # (see: [ https://en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes ])
    def GF(N):
    
      # N = 10 has been found to be impossible
      if N == 10: raise ValueError("impossible")
    
      # N = 12 is not known
      if N == 12: raise ValueError("not implemented")
    
      # if we can make a finite field of order N then it is possible
      try:
        import galois
        return galois.GF(N)
      except ValueError:
        pass
    
      # if N % 4 = 1 or 2, then N must be a sum of squares
      # (see: Bruck-Ryser-Chowla theorem)
      if N % 4 in (1, 2) and not any(is_square(N - i * i) for i in irange(1, isqrt(N))): raise ValueError("impossible")
      # and composite N is thought to be impossible anyway
      raise ValueError("not implemented")
    
    
    # make a card from seq, final (increment i)
    def _card(seq, final, i=1):
      s = list(seq)
      s.append(final)
      return tuple(sorted(x + i for x in s))
    
    # generate a set of cards
    def generate(K):
    
      # consider projective planes of order N = K - 1
      N = K - 1
      field = GF(N)
      S = field.elements()
    
      # first N * N cards
      for (i, j) in product(S, repeat=2):
        yield _card((field.add(field.mul(i, k), j) * N + k for k in S), N * N + i)
    
      # next N cards
      for i in S:
        yield _card(((j * N) + i for j in S), N * N + N)
    
      # final card
      yield _card((N * N + i for i in S), N * N + N)
    
    
    # verify a set of cards
    def verify(cards, k, n, verbose=1):
    
      r = Accumulator(fn=(lambda a, b: a & b), value=True)
    
      def check(text, value):
        if verbose: printf("  [{text} -> {value}]")
        r.accumulate(value)
    
      # check there are n cards
      check(f"{n} cards", len(cards) == n)
    
      # each with k symbols
      check(f"each card has {k} symbols", all(len(set(x)) == k for x in cards))
    
      # check there are n symbols
      symbols = set().union(*cards)
      check(f"{n} symbols", len(symbols) == n)
    
      # and each symbol appears on exactly k cards
      check(f"each symbol on exactly {k} cards", all(sum(1 for x in cards if s in x) == k for s in symbols))
    
      # and each pair of cards has exactly one symbol in common
      check(
        "each pair of cards has exactly 1 symbol in common",
        all(len(set(x).intersection(y)) == 1 for (x, y) in combinations(cards, 2))
      )
    
      return r.value
    
    
    k = arg(8, 0, int)
    n = k * k - k + 1
    printf("[k={k} n={n}]")
    
    try:
      cards = sorted(generate(k))
    except ValueError as e:
      printf("ERROR: {e}")
      exit()
    
    for (i, x) in enumerate(cards, start=1):
      printf("{i}: {x}")
    
    printf("[VERIFIED]" if verify(cards, k, n) else "[FAILED]")
    

    So, how do we implement Galois Fields GF(N), where N = p^n, I hear you ask?

    Some fields are easier to implement than others.

    For a start if n = 1 (i.e. N is a prime) then taking the integers modulo N, with the standard addition and multiplication operations (also modulo N), provides us with an implementation of GF(N).

    This is easily implemented by the [[ _GF_mod() ]] class in galois.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 Field GF(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 > 1 the construction is more complicated:

    Instead of integers we use polynomials (of degree less than n over the fields GF(p)). The operations are done modulo R, where R is an irreducible polynomial of degree n over GF(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 in galois.py), providing you have the irreducible polynomial available. In the code I provide irreducible polynomials up to n = 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 from enigma.py along with a couple extra polynomial routines we can implement the polynomial case for general GF(p^n). Again this is all fine, providing we have an appropriate irreducible polynomial. In the code I provided enough irreducible polynomials for all possible N up 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.py is given here: [ Wikipedia ].

    So at this point we have code that can construct any viable Galois Field.

    The code for galois.py is available on GitHub [ link ].

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: