Sunday Times Teaser 2538 – Octahedra

by Andrew Skidmore

Published: 15 May 2011 (link)

Fabule’s latest jewellery creation consists of a set of identically sized regular octahedra made of solid silver. On each octahedron, Fabule has gold-plated four of its eight equilateral triangle faces. No two octahedra are the same, but if Fabule had to make another, then it would be necessary to repeat one of the existing designs.

How many octahedra are there in the set?

One Comment Leave one →

Brian Gladman permalink


from itertools import permutations, product

# The faces of an octahedron have the same symmetries as the
# vertices of a cube so we can use the latter to create the
# transformations.  Using the vertex numbering scheme:
#
#    2---3
#    |\   \
#    | \   \
#    6- 1---4
#     \ | \ |
#      \|  \|
#       5---8
#
# the following symmetry transformations list where the vertex
# at index i goes to in the transformation

id =  (0, 1, 2, 3, 4, 5, 6, 7)   # identity

fr = ((1, 2, 3, 0, 5, 6, 7, 4),  # rotation about a face-face axes
      (4, 0, 3, 7, 5, 1, 2, 6),
      (3, 2, 6, 7, 0, 1, 5, 4))

vr = ((0, 3, 7, 4, 1, 2, 6, 5),  # rotation about vertex-vertex axes
      (5, 1, 0, 4, 6, 2, 3, 7),
      (5, 6, 2, 1, 4, 7, 3, 0),
      (2, 6, 7, 3, 1, 5, 4, 0))

er = ((3, 7, 4, 0, 2, 6, 5, 1),  # rotation about edge-edge axes
      (1, 0, 4, 5, 2, 3, 7, 6),
      (6, 2, 1, 5, 7, 3, 0, 4),
      (6, 7, 3, 2, 5, 4, 0, 1),
      (4, 7, 6, 5, 0, 3, 2, 1),
      (6, 5, 4, 7, 2, 1, 0, 3))

# perfrom the given combination of rotations
def rotate(x, cf, cv, ce):
  
  # rotations about each of the three face centres
  for i, r in enumerate(cf):
    for j in range(r):
      x = tuple(x[fr[i][k]] for k in range(8))
      
  # rotations about each of the four vertex diagonals
  for i, r in enumerate(cv):
    for j in range(r):
      x = tuple(x[vr[i][k]] for k in range(8))
      
  # rotations about each of the six edge diagonals
  for i, r in enumerate(ce):
    for j in range(r):
      x = tuple(x[er[i][k]] for k in range(8))

  return tuple(x)

def do_all_rotates(x):
  s = set()
  # do three face rotations (each 4 positions)
  for f in product(range(4), repeat=3):
    # do four vertex rotations (each 3 positions)
    for v in product(range(3), repeat=4):
      # do six edge rotations (each 2 positions)
      for e in product(range(2), repeat=6):
        y = rotate(x, f, v, e)
        # add to the set of octahedreon positions
        s |= set((y,))
  return s

# compile the set of all distinct symmetry transformations
# of a cube (and hence an octahedron)
cubes = do_all_rotates(id)

# compile the set of all vertex combinations of 4 golds and
# 4 silvers on an octahedron
octs = set(p for p in permutations([0] * 4 + [1] * 4, 8))

# now rotate each of these into all possible positions
# and keep a set of distinct octahedrons that result
unique_octs = set()
for oc in octs:
  # transform it and only add it to our list of octahedra
  # if no transform matches something already present
  for c in cubes:
    if tuple(oc[c[k]] for k in range(8)) in unique_octs:
      break
  else:
    unique_octs.add(oc)
print('There are {} octahedra in the set.'.format(len(unique_octs)))

from itertools import permutations, product

# The faces of an octahedron have the same symmetries as the

# vertices of a cube so we can use the latter to create the

# transformations. Using the vertex numbering scheme:

# 2---3

# |\ \

# | \ \

# 6- 1---4

# \ | \ |

# \| \|

# 5---8

# the following symmetry transformations list where the vertex

# at index i goes to in the transformation

id = (0, 1, 2, 3, 4, 5, 6, 7) # identity

fr = ((1, 2, 3, 0, 5, 6, 7, 4), # rotation about a face-face axes

(4, 0, 3, 7, 5, 1, 2, 6),

(3, 2, 6, 7, 0, 1, 5, 4))

vr = ((0, 3, 7, 4, 1, 2, 6, 5), # rotation about vertex-vertex axes

(5, 1, 0, 4, 6, 2, 3, 7),

(5, 6, 2, 1, 4, 7, 3, 0),

(2, 6, 7, 3, 1, 5, 4, 0))

er = ((3, 7, 4, 0, 2, 6, 5, 1), # rotation about edge-edge axes

(1, 0, 4, 5, 2, 3, 7, 6),

(6, 2, 1, 5, 7, 3, 0, 4),

(6, 7, 3, 2, 5, 4, 0, 1),

(4, 7, 6, 5, 0, 3, 2, 1),

(6, 5, 4, 7, 2, 1, 0, 3))

# perfrom the given combination of rotations

def rotate(x, cf, cv, ce):

# rotations about each of the three face centres

for i, r in enumerate(cf):

for j in range(r):

x = tuple(x[fr[i][k]] for k in range(8))

# rotations about each of the four vertex diagonals

for i, r in enumerate(cv):

for j in range(r):

x = tuple(x[vr[i][k]] for k in range(8))

# rotations about each of the six edge diagonals

for i, r in enumerate(ce):

for j in range(r):

x = tuple(x[er[i][k]] for k in range(8))

return tuple(x)

def do_all_rotates(x):

s = set()

# do three face rotations (each 4 positions)

for f in product(range(4), repeat=3):

# do four vertex rotations (each 3 positions)

for v in product(range(3), repeat=4):

# do six edge rotations (each 2 positions)

for e in product(range(2), repeat=6):

y = rotate(x, f, v, e)

# add to the set of octahedreon positions

s |= set((y,))

return s

# compile the set of all distinct symmetry transformations

# of a cube (and hence an octahedron)

cubes = do_all_rotates(id)

# compile the set of all vertex combinations of 4 golds and

# 4 silvers on an octahedron

octs = set(p for p in permutations([0] * 4 + [1] * 4, 8))

# now rotate each of these into all possible positions

# and keep a set of distinct octahedrons that result

unique_octs = set()

for oc in octs:

# transform it and only add it to our list of octahedra

# if no transform matches something already present

for c in cubes:

if tuple(oc[c[k]] for k in range(8)) in unique_octs:

break

else:

unique_octs.add(oc)

print('There are {} octahedra in the set.'.format(len(unique_octs)))

Sunday Times Teaser 2538 – Octahedra

by Andrew Skidmore

Published: 15 May 2011 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta