Sunday Times Teaser 3098 – Wonky Dice

by BRG on February 4, 2022

by Michael Fletcher

Published Sunday February 06 2022 (link)

I have two octahedral (eight-faced) dice. There are positive whole numbers (not necessarily all different) on each of their faces. I throw the two dice and add the two numbers that are showing on the top faces. The probability of a total of 2 is 1/64, the probability of a total of 3 is 2/64 and so on. The probabilities of the totals are the same as for a pair of standard octahedral dice (each numbered 1 to 8). Interestingly, however, the highest number on the first die is 11.

What are the eight numbers (in ascending order) on the second die?

From → Uncategorized

3 Comments Leave one →

Brian Gladman permalink

Fast to write, slow to run.


from itertools import combinations_with_replacement as cwr

# generate the probabilities for a standard
# pair of octahedral dice
sm = [0] * 24
for i in range(1, 9):
  for j in range(1, 9):
    sm[i + j] += 1

# consider the possible numbers on the seven 
# faces of the 1st dice with numbers up to 10
for d16 in cwr(range(2, 11), 6):
  # add the eigth face number (11)
  d1 = (1,) + d16 + (11,)
  
  # consider the possible numbers on the seven 
  # faces of the 2nd dice with numbers up to 5
  for d26 in cwr(range(2, 5), 6):
    d2 = (1,) + d26 + (5,)
    sw = [0] * 24
    for i in range(8):
      for j in range(8):
        ij = d1[i] + d2[j]
        sw[ij] += 1
    # output any dice combinations that give the
    # same results as standard octahedral dice
    if sw == sm:
      print(f"{d2} {list(d1)}")

from itertools import combinations_with_replacement as cwr

# generate the probabilities for a standard

# pair of octahedral dice

sm = [0] * 24

for i in range(1, 9):

for j in range(1, 9):

sm[i + j] += 1

# consider the possible numbers on the seven

# faces of the 1st dice with numbers up to 10

for d16 in cwr(range(2, 11), 6):

# add the eigth face number (11)

d1 = (1,) + d16 + (11,)

# consider the possible numbers on the seven

# faces of the 2nd dice with numbers up to 5

for d26 in cwr(range(2, 5), 6):

d2 = (1,) + d26 + (5,)

sw = [0] * 24

for i in range(8):

for j in range(8):

ij = d1[i] + d2[j]

sw[ij] += 1

# output any dice combinations that give the

# same results as standard octahedral dice

if sw == sm:

print(f"{d2} {list(d1)}")

There is an elegant theory for analysing dice combinations using generating functions. This program uses this approach to give a faster solution using my Python polynomial library. This runs in 15 milliseconds (profile timing).


from itertools import product
from polynomial import Poly, cyclotomic

# find dice pairs giving the same probabilties as
# standard dice pairs
def sicherman(n):

  # return the dice represented by a polynomial
  def die(ct):
    if sum(ct) == n and all(c >= 0 for c in ct):
      return sum(((i,) * c for i, c in enumerate(ct, 1)), ())

  # form the polynomial representation of a fair octagonal
  # die as the product of cyclotomic polynomials (less the
  # factor of x)
  # (see https://en.wikipedia.org/wiki/Sicherman_dice)
  fctrs = []
  for d in range(2, n + 1):
    if n % d == 0:
      fctrs.append(cyclotomic(d))
  
  # consider all subsets of the factors of this polynomial
  for ms in product((0, 1, 2), repeat=len(fctrs)):
    p1, p2 = Poly([1]), Poly([1]) 
    for m, f in zip(ms, fctrs):
      mp = (1, f, f * f)
      p1 *= mp[m]
      p2 *= mp[2 - m]
    d1 = die(p1)
    if d1:
      d2 = die(p2)
      if d2 and d1[-1] <= d2[-1]:
        yield d1, d2

for d1, d2 in sicherman(8):
  if d2[-1] == 11:
    print(f"{d1}  {d2}")

from itertools import product

from polynomial import Poly, cyclotomic

# find dice pairs giving the same probabilties as

# standard dice pairs

def sicherman(n):

# return the dice represented by a polynomial

def die(ct):

if sum(ct) == n and all(c >= 0 for c in ct):

return sum(((i,) * c for i, c in enumerate(ct, 1)), ())

# form the polynomial representation of a fair octagonal

# die as the product of cyclotomic polynomials (less the

# factor of x)

# (see https://en.wikipedia.org/wiki/Sicherman_dice)

fctrs = []

for d in range(2, n + 1):

if n % d == 0:

fctrs.append(cyclotomic(d))

# consider all subsets of the factors of this polynomial

for ms in product((0, 1, 2), repeat=len(fctrs)):

p1, p2 = Poly([1]), Poly([1])

for m, f in zip(ms, fctrs):

mp = (1, f, f * f)

p1 *= mp[m]

p2 *= mp[2 - m]

d1 = die(p1)

if d1:

d2 = die(p2)

if d2 and d1[-1] <= d2[-1]:

yield d1, d2

for d1, d2 in sicherman(8):

if d2[-1] == 11:

print(f"{d1} {d2}")

There are four fair octagonal dice pairs:


(1, 2, 3, 4, 5, 6, 7, 8) [1, 2, 3, 4, 5, 6, 7, 8]
(1, 2, 3, 3, 4, 4, 5, 6) [1, 2, 5, 5, 6, 6, 9, 10]
(1, 2, 2, 3, 5, 6, 6, 7) [1, 3, 3, 5, 5, 7, 7, 9]
(1, 2, 2, 3, 3, 4, 4, 5) [1, 3, 5, 5, 7, 7, 9, 11]

(1, 2, 3, 4, 5, 6, 7, 8) [1, 2, 3, 4, 5, 6, 7, 8]

(1, 2, 3, 3, 4, 4, 5, 6) [1, 2, 5, 5, 6, 6, 9, 10]

(1, 2, 2, 3, 5, 6, 6, 7) [1, 3, 3, 5, 5, 7, 7, 9]

(1, 2, 2, 3, 3, 4, 4, 5) [1, 3, 5, 5, 7, 7, 9, 11]

John Z permalink

using recursion seems fast


# chances for standard dice
sdc = [0] * 17
for i in range(1, 9):
  for j in range(1, 9):
    sdc[i + j] += 1


def dice8(wd1 = (1,), wd2 = (1,)):
  global sdc

  if len(wd1) == 7:
    yield wd1 +(11,), wd2 + (5,)

  else:
    for i in range(1, 5):
      # temporary wonky die 2
      twd2 = wd2 + (i, 5)
      for j in range(1, 11):
        # temporary wonky die 1
        twd1 = wd1 + (j, 11)

        wdc = [0] * 17
        k = len(twd1)
        for m in range(k):
          for n in range(k):
            ij = twd1[m] + twd2[n]
            wdc[ij] += 1
            
        # tweaking this 'if' statement may improve speed
        # beginning part of list of chances must be equal
        if wdc[:(i + j) // 2] != sdc[:(i + j) // 2]:
          break
        
        # chances for wonky dice must never exceed those of standard dice
        if any(wdc[p] > sdc[p] for p in range(17)):
          continue

        yield from dice8(wd1 + (j,), wd2 + (i,))

for dice in dice8():
  print(dice)
  break

# chances for standard dice

sdc = [0] * 17

for i in range(1, 9):

for j in range(1, 9):

sdc[i + j] += 1

def dice8(wd1 = (1,), wd2 = (1,)):

global sdc

if len(wd1) == 7:

yield wd1 +(11,), wd2 + (5,)

else:

for i in range(1, 5):

# temporary wonky die 2

twd2 = wd2 + (i, 5)

for j in range(1, 11):

# temporary wonky die 1

twd1 = wd1 + (j, 11)

wdc = [0] * 17

k = len(twd1)

for m in range(k):

for n in range(k):

ij = twd1[m] + twd2[n]

wdc[ij] += 1

# tweaking this 'if' statement may improve speed

# beginning part of list of chances must be equal

if wdc[:(i + j) // 2] != sdc[:(i + j) // 2]:

break

# chances for wonky dice must never exceed those of standard dice

if any(wdc[p] > sdc[p] for p in range(17)):

continue

yield from dice8(wd1 + (j,), wd2 + (i,))

for dice in dice8():

print(dice)

break

Frits permalink

Quite fast and even a lot faster (10ms) with:


for i in range(2 if len(wd2) == 1 else wd2[-1], 5):
  # temporary wonky die 2
  twd2 = wd2 + (i, 5)
  for j in range(2 if len(wd1) == 1 else wd1[-1], 11):

for i in range(2 if len(wd2) == 1 else wd2[-1], 5):

# temporary wonky die 2

twd2 = wd2 + (i, 5)

for j in range(2 if len(wd1) == 1 else wd1[-1], 11):

Sunday Times Teaser 3098 – Wonky Dice

by Michael Fletcher

Published Sunday February 06 2022 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta