Enigmatic Code

Programming Enigma Puzzles

Enigma 1652: A colourful lamp

From New Scientist #2818, 25th June 2011 [link]

My artistic nephew is making a lamp which involves using the largest possible number of regular tetrahedra – solid bodies with four faces, each an equilateral triangle – whose faces will be painted with various colours. These will float in a fluid that is agitated and then lit from beneath by a bright light to produce a sparkling effect.

Some of the tetrahedra will have all faces the same colour, some will have faces of two different colours, others three and others four, but no two tetrahedra will be identical. Having done his sums, he finds that he will have exactly the same number of tetrahedra with four different colours as have three.

How many colours will he use? And how many tetrahedra?

[enigma1652]

Advertisements

2 responses to “Enigma 1652: A colourful lamp

  1. jimrandell 5 December 2011 at 4:35 pm

    Here’s a constructive approach (which is the type of solution I like) that generates all the possibilities for coloured tetrahedra and reduces it by the ones that are equivalent by rotation.

    The following Python code runs in 88ms.

    from itertools import product, count
    
    def rotations(a, b, c, d):
      # the rotations of a tetrahedron
      return ((a, b, c, d), (a, d, b, c), (a, c, d, b),
              (b, a, d, c), (b, c, a, d), (b, d, c, a),
              (c, a, b, d), (c, d, a, b), (c, b, d, a),
              (d, a, c, b), (d, b, a, c), (d, c, b, a))
    
    def colourings(n):
      # count the number of 1,2,3,4-colourings from n difference colours
      c = dict((i, 0) for i in range(1, 5))
      s = set()
      for x in product(range(n), repeat=4):
        r = rotations(*x)
        if not s.intersection(r):
          c[len(set(x))] += 1
          s.update(r)
      return c
    
    for i in count(4):
      c = colourings(i)
      if c[3] == c[4]:
        print(i, c, sum(c.values()))
        break
    

    Solution: There are 9 colours, and 621 tetrahedra.

  2. Jim Randell 5 December 2011 at 4:36 pm

    And here’s an analytical approach (with a trivial amount of programming).

    # according to Wolfram Alpha http://mathworld.wolfram.com/PolyhedronColoring.html
    # there are following distinct colourings of tetrahedra with m (or fewer) colours:
    # T'(m) = 1, 5, 15, 36
    
    # so for distinct colourings with exactly m colours we have:
    # T(m) = 1, T'(2) - 2.T(1), T'(3) - 3C2.T(2) - 3C1.T(1), T'(4) - 4C3.T(3) - 4C2.T(2) - 4C1.T(1)
    # where nCk = n!/(k!(n-k)!), so T(m) = 1, 3, 3, 2
    
    # so lets suppose we have n colours...
    
    # there are: n*T(1)
    # = n 1-colour tetrahedra [1]
    
    # there are: nC2 = n(n-1)/2 combinations of two colours, and T(2) colourings
    # = 3n(n-1)/2 2-colour tetrahedra [2]
    
    # there are nC3 = n(n-1)(n-2)/(3x2) combinations of 3 colours, and T(3) colourings
    # = n(n-1)(n-2)/2 3-colour tetrahedra [3]
    
    # there are nC4 = n(n-1)(n-2)(n-3)/(4x3x2) combinations of 4 colours, and T(4) colourings
    # = n(n-1)(n-2)(n-3)/12 4-colour tetrahedra [4]
    
    # as [3] = [4]
    # n(n-1)(n-2)/2 = n(n-1)(n-2)(n-3)/12
    # 1/2 = (n-3)/12
    # 6 = n-3
    # 9 = n
    
    # so...
    n = 9
    print("number of colours = {n}".format(n=n))
    
    # and the number of tetrahedra is...
    div = lambda a, b: a // b
    t1 = n
    t2 = div(3 * n * (n - 1), 2)
    t3 = div(n * (n - 1) * (n - 2), 2)
    t4 = div(n * (n - 1) * (n - 2) * (n - 3), 12)
    print("number of tetrahedra = {t1}+{t2}+{t3}+{t4} = {t}".format(t1=t1, t2=t2, t3=t3, t4=t4, t=t1 + t2 + t3 + t4))
    

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: