Sunday Times Teaser 3207 – Dodecahedra

by BRG on March 8, 2024

by Andrew Skidmore

Published Friday March 08 2024 (link)

Fabulé’s next creation will be a set of equal-sized silver regular dodecahedra, but some of the faces will be gold-plated. He is undecided whether to go ahead with either a “Charm” set or a “Partial” set.

“Charm” is composed of dodecahedra with at least one gold-plated face but with no gold-plated face having a common side with more than one other gold-plated face. “Partial” is composed of dodecahedra with exactly six gold-plated faces. All the items in each set are distinguishable.

What is the maximum number of dodecahedra possible in (a) “Charm” (b) “Partial”?

From → Uncategorized

One Comment Leave one →

BRG permalink

The most difficult part of this teaser is that of identifying if two given polyhedrons with some gold faces are distinct or just rotations of each other. And here I have shamelessly copied Jim Randell’s approach. I did look at a number of Python libraries that are capable of doing this but they are quite sophisticated and would take a considerable amount of time to learn how to use.


from itertools import combinations

# arrangement of adjacent faces
f2afs = {
  0: [1, 2, 3, 4, 5],
  1: [0, 5, 8, 7, 2],
  2: [0, 1, 7, 6, 3],
  3: [0, 2, 6, 10, 4],
  4: [0, 3, 10, 9, 5],
  5: [0, 4, 9, 8, 1],
}
# add in the opposite faces
f2afs.update((11 - k, list(11 - v for v in fs[::-1]))
                  for k, fs in list(f2afs.items()))

# Credit: Jim Randell
# construct the sixty rotations of a dodecahedron with
# face numbers 0 to 11 (opposite faces adding to 11) 

# Put each top half face in turn at the top of the
# dodecahedron and rotate its adjacent faces into 
# the five face positions immediately below the top
rots = []
for k, fs in f2afs.items():
  for _ in fs:
    r = [k] + fs
    r.extend(list(11 - f for f in r)[::-1])
    rots.append(r)
    fs = list(fs[1:]) + [fs[0]]

# apply a rotation to a set of faces
rot = lambda r, fs: tuple(sorted(r[f] for f in fs))
# canonical colouring for a set of faces
canonical = lambda fs: min(rot(r, fs) for r in rots)

sols = set()
# the number of gold faces 
for lf in range(1, len(f2afs.keys())):
  c2fs = dict()
  # choose which faces are gold 
  for fs in combinations(f2afs.keys(), lf):
    # ensure that each gold face has less than two adjacent gold faces
    if all(sum(1 if f in f2afs[f1] else 0 for f in fs) < 2 for f1 in fs):
      cfs = canonical(fs)
      c2fs[cfs] = c2fs.get(cfs, []) + [fs]
      sols.add(cfs)
  if c2fs:
    ts = ', '.join(f"{s_fs[0]}: {len(s_fs)}" for cf, s_fs in c2fs.items())
    print(f"{lf} gold faces; {len(c2fs.keys())} "
          f"equivalence groups (faces:numbers): {ts}")
print(f"\n(a) Charm:   {len(sols)} dodecahedra")

sols = set()
# consider all arrangements with six gold faces
for p in combinations(f2afs.keys(), 6):
  sols.add(canonical(p))
print(f"(b) Partial: {len(sols)} dodecahedra")

from itertools import combinations

# arrangement of adjacent faces

f2afs = {

0: [1, 2, 3, 4, 5],

1: [0, 5, 8, 7, 2],

2: [0, 1, 7, 6, 3],

3: [0, 2, 6, 10, 4],

4: [0, 3, 10, 9, 5],

5: [0, 4, 9, 8, 1],

}

# add in the opposite faces

f2afs.update((11 - k, list(11 - v for v in fs[::-1]))

for k, fs in list(f2afs.items()))

# Credit: Jim Randell

# construct the sixty rotations of a dodecahedron with

# face numbers 0 to 11 (opposite faces adding to 11)

# Put each top half face in turn at the top of the

# dodecahedron and rotate its adjacent faces into

# the five face positions immediately below the top

rots = []

for k, fs in f2afs.items():

for _ in fs:

r = [k] + fs

r.extend(list(11 - f for f in r)[::-1])

rots.append(r)

fs = list(fs[1:]) + [fs[0]]

# apply a rotation to a set of faces

rot = lambda r, fs: tuple(sorted(r[f] for f in fs))

# canonical colouring for a set of faces

canonical = lambda fs: min(rot(r, fs) for r in rots)

sols = set()

# the number of gold faces

for lf in range(1, len(f2afs.keys())):

c2fs = dict()

# choose which faces are gold

for fs in combinations(f2afs.keys(), lf):

# ensure that each gold face has less than two adjacent gold faces

if all(sum(1 if f in f2afs[f1] else 0 for f in fs) < 2 for f1 in fs):

cfs = canonical(fs)

c2fs[cfs] = c2fs.get(cfs, []) + [fs]

sols.add(cfs)

if c2fs:

ts = ', '.join(f"{s_fs[0]}: {len(s_fs)}" for cf, s_fs in c2fs.items())

print(f"{lf} gold faces; {len(c2fs.keys())} "

f"equivalence groups (faces:numbers): {ts}")

print(f"\n(a) Charm: {len(sols)} dodecahedra")

sols = set()

# consider all arrangements with six gold faces

for p in combinations(f2afs.keys(), 6):

sols.add(canonical(p))

print(f"(b) Partial: {len(sols)} dodecahedra")

Sunday Times Teaser 3207 – Dodecahedra

by Andrew Skidmore

Published Friday March 08 2024 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta