Enigmatic Code

Programming Enigma Puzzles

Enigma 1124: Classy glass

From New Scientist #2280, 3rd March 2001 [link]

On each anniversary of its foundation my company asks a local artist to make a glass sculpture consisting of a three-by-three arrangement of squares of glass. On the first anniversary just one of the squares had to be red, the rest being blue. On the second anniversary two of the nine had to be red, the rest blue, etc. Before making the final work the artist produces scale models of all the possibilities so that we can choose the one we like best. For economy she does not make any two that look the same when rotated or turned over. So, for example, her first anniversary models were as illustrated, involving a total of just three red squares:

enigma-1124

For our current anniversary she has again produced scale models of all the possibilities, and for these she has had to make more than one hundred small red squares of glass.

Which anniversary is it, and precisely how many small red squares does she need?

[enigma1124]

Advertisements

6 responses to “Enigma 1124: Classy glass

  1. Jim Randell 13 March 2017 at 8:19 am

    The grid is fairly small, so programatically we can just generate all possible colourings of the grid with n red squares, and then combine colourings that are the same by rotation/reflection.

    This Python program examines the number of red and blue squares for anniversaries from 0 to 9. It runs in 57ms.

    from itertools import combinations
    from enigma import irange, printf
    
    # label the grid
    square = (0, 1, 2, 3, 4, 5, 6, 7, 8)
    
    # symmetries of the grid
    grids = (
      # rotations
      (0, 1, 2, 3, 4, 5, 6, 7, 8),
      (6, 3, 0, 7, 4, 1, 8, 5, 2),
      (8, 7, 6, 5, 4, 3, 2, 1, 0),
      (2, 5, 8, 1, 4, 7, 0, 3, 6),
      # reflections
      (2, 1, 0, 5, 4, 3, 8, 7, 6),
      (8, 5, 2, 7, 4, 1, 6, 3, 0),
      (6, 7, 8, 3, 4, 5, 0, 1, 2),
      (0, 3, 6, 1, 4, 7, 2, 5, 8),
    )
    
    # canonical representation of a pattern
    def canonical(grid):
      return min(tuple(grid[r[i]] for i in square) for r in grids)
    
    # number of red squares
    for n in irange(0, 9):
      r = set()
      # choose red squares
      for s in combinations(square, n):
        # make the grid
        grid = tuple((1 if i in s else 0) for i in square)
        r.add(canonical(grid))
    
      # count the number of different grids and number of red squares
      gs = len(r)
      rs = n * gs
      bs = (9 - n) * gs
      s = ('[*** SOLUTION ***]' if rs > 100 else '')
      printf("n={n}, grids={gs}, red={rs}, blue={bs} {s}")
    

    Solution: It is the fifth anniversary. 115 red squares are required.

    Of course the numbers of red and blue tiles required for anniversary n are the same as the number of blue and red tiles required for anniversary 9 – n.

    Here’s the output of the program, with the number of different grids and the number of red and blue tiles required for each anniversary:

    n=0, grids=1, red=0, blue=9 
    n=1, grids=3, red=3, blue=24 
    n=2, grids=8, red=16, blue=56 
    n=3, grids=16, red=48, blue=96 
    n=4, grids=23, red=92, blue=115 
    n=5, grids=23, red=115, blue=92
    n=6, grids=16, red=96, blue=48 
    n=7, grids=8, red=56, blue=16 
    n=8, grids=3, red=24, blue=3 
    n=9, grids=1, red=9, blue=0
    
  2. Hugh Casement 13 March 2017 at 2:13 pm

    On the first anniversary there are 9 configurations, including reflexions and/or rotations.
    On the second, 36 which is the 8th triangular number = 8×9/2!.
    On the third, 84 which is the 7th tetrahedral number = 7×8×9/3!.
    On the fourth, 126 = 6×7×8×9/4!, which I suppose we can call the 6th four-dimensional tetrahedral number.
    Continuing in like manner we find (not surprisingly) that the numbers continue 126, 84, 36, 9, 1.

  3. Brian Gladman 13 March 2017 at 4:26 pm
    from itertools import product
    from collections import defaultdict
    
    # 3x3 configurations are kept as an array of nine values: three
    # for row 1, three for row 2 and then three for row 3
    
    # the index of the old position for each position when rotated
    ixr = (6, 3, 0, 7, 4, 1, 8, 5, 2)
    # the index of the old position for each position when turned over
    ixo = (2, 1, 0, 5, 4, 3, 8, 7, 6)
    
    # check if a 3x3 configuration is in a set of such configurations
    # by testing all four rotations in normal and overturned states
    def is_in(sq, set_sqr):
      s = sq[:]
      for i in range(2):
        s = tuple(s[k] for k in ixo)
        t = s[:]
        for j in range(4):
          t = tuple(t[k] for k in ixr)
          if t in set_sqr[sq.count(1)]:
            return True
      return False
    
    # keep 3x3 configuations indexed on their number of reds
    sqrs = defaultdict(set)
    # form all possible 3x3 configurations
    for sq in product((0, 1), repeat=9):
      # if we have not yet seen this configuration 
      if not is_in(sq, sqrs):
        # .. add it to our set for this number of red squares
        sqrs[sq.count(1)].add(sq)
    
    # output the results
    print('Red  3x3 Totals Red Blue')
    for r in range(10):
      c = len(sqrs[r])
      print(f'{r:>3}{c:>5}{c*r:>11}{c*(9-r):>5}')
    
  4. arthurvause 14 March 2017 at 9:41 am

    The number of distinct ways of selecting M items in an N*N grid, unique up to rotation and reflection, is a well known problem.

    This stackexchange question sketches the explanation of the solution, from which I have produced the code below, although I don’t claim to fully follow the derivation.

    import sympy
         
    def solutions(N):
      # number of ways of choosing objects in an N*N grid, up to rotation and reflection
      # from https://math.stackexchange.com/questions/570003/how-many-unique-patterns-exist-for-a-nxn-grid
    
      x = sympy.symbols('x')
      if N%2 == 0:
        p = ((1+x)**(N*N)+ 3 * (1+x*x)**((N*N)/2) + 2*(1+x)**N *(1+x*x)**( (N*N-N)/2 ) +2*(1+x**4)**( (N*N)/4 ))/8
      else:
        p = ((1+x)**(N*N)+ 4*(1+x)**N * (1+x*x)**((N*N-N)/2) + 2*(1+x)*(1+x**4)**( (N*N-1)/4 ) +(1+x)*(1+x*x)**( (N*N-1)/2 ))/8
    
      return sympy.Poly(p,x).all_coeffs() 
      
    for a, n in enumerate( solutions(3) ):
      if a*n > 100:
        print "Anniversary number {} needs {} red squares".format(a,a*n)
    
    • arthurvause 14 March 2017 at 10:06 am

      Of course, for this problem, the solutions for even values of N aren’t needed, but I have used the function in another program to verify that it correctly reproduces OEIS sequence A019318.

    • Jim Randell 14 March 2017 at 2:52 pm

      That’s neat. I ended up on that page on StackExchange yesterday, but got lost in all the talk of the Orbit-counting Lemma, the Cycle Index Theorem, and Pólya enumeration, and eventually decided that it was a bit of overkill for the 3×3 grid anyway.

      But thanks for extracting the formulae. Here’s a version that uses the Polynomial class from the enigma.py library, which saves having to pull in SymPy, so is a bit quicker.

      (I added the polynomial routines after the discussion on generating polynomials for Pizza Puzzle).

      The size of grid N can be specified on the command line (defaults to 3) and the number of different grids (patterns), red tiles and blue tiles are given for each n = 0..N².

      The number of grids found corresponds with OEIS A054252.

      from enigma import Polynomial, arg, printf
      
      # find the number of different 2-colourings on an NxN grid
      # patterns that are the same when rotated/reflected are counted once
      # return a tuple with N^2 elements corresponding to the number
      # of different patterns with n elements selected
      def solve(N):
        # constants
        k2 = Polynomial([2]) # 2
        k3 = Polynomial([3]) # 3
        k4 = Polynomial([4]) # 4
        # polynomials
        p1 = Polynomial([1, 1]) # 1 + x
        p2 = Polynomial([1, 0, 1]) # 1 + x^2
        p4 = Polynomial([1, 0, 0, 0, 1]) # 1 + x^4
        # exponents (that work with even and odd parity N)
        e1 = N * N # N^2
        e2 = e1 // 2 # (1/2)(N^2) or (1/2)(N^2 - 1)
        e3 = (e1 - N) // 2 # (1/2)(N^2 - N)
        e4 = e2 // 2 # (1/4)(N^2) or (1/4)(N^2 - 1)
      
        # construct the generating polynomial
        if N % 2 == 0:
          # even N
          p = (p1 ** e1) + (k3 * (p2 ** e2)) + (k2 * (p1 ** N) * (p2 ** e3)) + (k2 * (p4 ** e4))
        else:
          # odd N
          p = (p1 ** e1) + (p1 * (p2 ** e2)) + (k4 * (p1 ** N) * (p2 ** e3)) + (k2 * p1 * (p4 ** e4))
      
        # divide the coefficients by 8
        (s, r) = zip(*(divmod(a, 8) for a in p))
        assert all(x == 0 for x in r)
        return s
      
      # size of the grid
      N = arg(3, 0, int)
      N2 = N * N
      
      # consider the NxN grid
      for (n, g) in enumerate(solve(N)):
        # number of red and blue squares
        (rs, bs) = (n * g, (N2 - n) * g)
        printf("[N={N}] n={n}: grids={g}, reds={rs}, blues={bs}")
      

      For the N=3 case it runs in 42ms.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: