Sunday Times Teaser 2739 – Funny Dice

by Michael Fletcher

Published: 22 March 2015 (link)

I have two cube-shaped dice, one red and one blue, with a positive whole number on each face. When I throw the dice and add up the two numbers, the most likely total is 7. The next most likely totals are 6 and 8, the next are 5 and 9, the next are 4 and 10, the next are 3 and 11, and the least likely are 2 and 12. However, my dice are not standard: indeed, the total of the six numbers on the red dice is higher than the total of those on the blue dice.

What are the six numbers on the red dice?

6 Comments Leave one →

Brian Gladman permalink


from itertools import combinations_with_replacement, product
from collections import defaultdict

# both dice must have ones; one die must have a two in order
# to allow a combined score of three; the other die then has
# a maximum face value of ten to avoid a score above twelve;
# since sums of 2 and twelve are equally likely, the maximum
# values on each die can only occur once

# calculate dice pair probabilitie3s
def dp_prob(a, b):
  s = [0] * 13
  for i in a:
    for j in b:
      s[i + j] += 1
  return s
      
# probabilities for standard dice
sd = dp_prob(range(1, 7), range(1, 7))

# the maximum face value for the die without the known two
for d_max in range(2, 11):

  # list the possible dice without the known two
  for c4 in combinations_with_replacement(range(1, d_max), 4):
    da = (1,) + c4 + (d_max,)

    # list the possible dice with the known two
    for c3 in combinations_with_replacement(range(1, 12 - d_max), 3):
      db = (1, 2) + c3 + (12 - d_max,)
        
      dp = dp_prob(da, db)
      if dp == sd and da != db:
        blue, red = (da, db) if sum(da) < sum(db) else (db, da)
        print('red = {}, blue = {}'.format(red, blue))

from itertools import combinations_with_replacement, product

from collections import defaultdict

# both dice must have ones; one die must have a two in order

# to allow a combined score of three; the other die then has

# a maximum face value of ten to avoid a score above twelve;

# since sums of 2 and twelve are equally likely, the maximum

# values on each die can only occur once

# calculate dice pair probabilitie3s

def dp_prob(a, b):

s = [0] * 13

for i in a:

for j in b:

s[i + j] += 1

return s

# probabilities for standard dice

sd = dp_prob(range(1, 7), range(1, 7))

# the maximum face value for the die without the known two

for d_max in range(2, 11):

# list the possible dice without the known two

for c4 in combinations_with_replacement(range(1, d_max), 4):

da = (1,) + c4 + (d_max,)

# list the possible dice with the known two

for c3 in combinations_with_replacement(range(1, 12 - d_max), 3):

db = (1, 2) + c3 + (12 - d_max,)

dp = dp_prob(da, db)

if dp == sd and da != db:

blue, red = (da, db) if sum(da) < sum(db) else (db, da)

print('red = {}, blue = {}'.format(red, blue))

Peter Hayes permalink

I’m personally of the opinion that “non-standard dice” are too well-known for this teaser to pass the “originality” test.

Reply
michael fletcher permalink

A bit easy – how about if the dice are twelve sided – what are the numbers on each dice – or even if the dice have 2N sides what are the numbers on each dice?

Reply
- Brian Gladman permalink
  
  I suspect that is only easy if you have experienced it (or something like it) before – we can see from my site for manual solvers (https://sites.google.com/site/sundaytimesteasers/teaser-index-1/2015-q1/teaser-2739) that it created quite a bit of discussion.
  
  I have written to Victor Bryant about ‘originality’ before now and his view is that there are very few truly original teasers so it would make life hard if he insisted on using this as a criterion.
  
  For me it opened up an area I had not delved into before (I had looked at non-transitive dice but not non-standard ones). So I certainly enjoyed this one both intellectually and as a programming exercise – well done!
  
  For those who are interested, here is a link covering the non-standard dice https://en.wikipedia.org/wiki/Sicherman_dice.
  
  Reply
Peter Hayes permalink

Assume the use of two dodecahedral dice numbered 1 to 12. The same probability distribution can then also be obtained by the use of any of the following seven combinations:

(1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7) and (1, 3, 5, 7, 7, 9, 9, 11, 11, 13, 15, 17);

(1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9) and (1, 2, 3, 7, 7, 8, 8, 9, 9, 13, 14, 15);

(1, 2, 4, 5, 5, 6, 8, 9, 9, 10, 12, 13) and (1, 2, 3, 3, 4, 5, 7, 8, 9, 9, 10, 11);

(1, 2, 2, 3, 5, 6, 6, 7, 9, 10, 10, 11) and (1, 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13);

(1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6) and (1, 4, 5, 7, 8, 9, 10, 11, 12, 14, 15, 18);

(1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8) and (1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16);

(1, 2, 2, 3, 3, 4, 7, 8, 8, 9, 9, 10) and (1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14).

I worked this out by hand (and spreadsheet) after work and before dinner.

I believe it is exhaustive; it exhausted me.

But thank you. “It was a tough assignment.”

Reply

Brian Gladman permalink

Peter Hayes has alerted me to a neat way of tackling non-standard dice using a mathematical method based on generating functions. The idea is that the six faces on a die can be represented by the polynomial: \[x+x^2+x^3+x^4+x^5+x^6\]where the powers of \(x\) represent the face values on the die and the polynomial coefficients represent the number of times each face value occurs. The above polynomial hence represents a standard die. If we now throw two dice, we can find the result by squaring the above polynomial to give:\[x^2+2x^3+3x^4+4x^5+5x^6+6x^7+5x^8+4x^9+3x^{10}+2x^{11}+x^{12}\]Now the powers represent the sum of the two dice and the coefficients give the number of times each sum will occur. So sums of 2 and 12 each occur just once, while a sum of 7 occurs 6 times (1+6, 2+5, 3+4, 4+3, 5+2, 6+1).

It turns out that the generating polynomial for a standard six sided can be factored:\[x+x^2+x^3+x^4+x^5+x^6=x(x+1)(x^2-x+1)(x^2+x+1)\] and this allows the result of throwing two standard dice to be represented by the polynomial:\[x^2(x+1)^2(x^2-x+1)^2(x^2+x+1)^2\] Although for two standard dice we select the same factors for each die, we can produce the same result from other selections of the two subsets. For example we might chose the two subsets: \[x(x+1)(x^2-x+1)=x+x^4\]\[x(x+1)(x^2+x+1)^2(x^2-x+1)=x+2x^2+3x^3+3x^4+3x^5+3x^6+2x^7+x^8\]These two polynomials give a two sided die (1, 4) and an 18 sided one (1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8). In addition to different numbers of faces, other choices can also involve negative face values but just one: \[x(x+1)(x^2+x+1)=x+2x^2+2x^3+x^4\] \[x(x+1)(x^2+x+1)(x^2-x+1)^2=x+x^3+x^4+x^5+x^6+x^8\] produces a pair of six-sided dice. It is these dice with face values (1, 2, 2, 3, 3, 4) and (1, 3, 4, 5, 6, 8) that solve this teaser. They were first discovered by George Sicherman and are named after him (see Sicherman Dice for more details).

Here is a Python program that looks for N sided non-standard dice using a generalisation of these ideas.


from sys import argv
from itertools import combinations
from functools import reduce
from operator import mul

from number_theory import factors, divisors
from polynomial import Poly

# generate cyclotomic polynomials
def cyclotomic(n):
  # phi(1)
  phi = Poly([-1, 1])
  if n == 1:
    return phi
  # find unique prime factors of n
  f = set(factors(n))
  # If p is a prime that does not divide m then phi(m.p)[x]  =
  # phi(m)[x^p] / phi(m)[x]. So starting with p, the 1st prime 
  # in f we have phi(1.p)[x] = phi(1)[x^p] / phi(1)[x]. And we
  # can then repeat this process for the next prime in f  (say
  # q) to show that phi(p.q)[x] = phi(p)[x^q] / phi(q)[x].  We
  # can continue this for all primes in f. 
  for p in f:
    phi, rem = divmod(phi.compose(Poly([(1, p)])), phi)
  # we can now account for any squared component in f using
  # the identity phi(n)[x] = phi(q)[x^(n/q)] where q is the
  # product of the distinct prime factors of n
  return phi.compose(Poly([(1, n // reduce(mul, f, 1))]))

# output the face values of a die specified by polynomial p
def die(p):
  d = []
  for e, v in enumerate(p.coeff):
    d += [e] * v
  return tuple(sorted(d))

# generate pairs of dice giving the same results when thrown
# and added as two identical n-faced dice numbered from 1 to
# n (only dice with equal numbers of faces if same is True)
def dice_pairs(n, same=True):
  # for saving solutions
  sol = []
  # holds the cyclotomic polynomial factorisatiosn of the dice 
  # generating polynomial x + x^2 + ... + x^faces  
  l_poly = []
  for d in divisors(faces):
    if d > 1:
      l_poly += [cyclotomic(d)]
  ln_poly = len(l_poly)
  l_p2 = l_poly + l_poly
  # now choose the number of polynomial factors for the
  # first die
  for nf in range(1, ln_poly + 1):
    # check all combinations of this number of polynomials
    for f in combinations(range(len(l_p2)), nf):
      # list the polynomials for the first die  
      t = [l_p2[i] for i in f]
      # multiply them (and x) for the polynomial for the first die
      p1 = reduce(mul, t, Poly([0, 1]))
      # list the remaining polynomials for the second die
      t = [l_p2[i] for i in range(len(l_p2)) if i not in f]
      # multiply them (and x) for the polynomial for the second die
      p2 = reduce(mul, t, Poly([0, 1]))
      # all polynomial coefficients must be non-negative without zeros
      if all(x >= 0 for x in p1.coeff + p2.coeff) and p1(0) == p2(0):
        # if necessary check that the dice have the same number of faces
        if not same or p1(1) == p2(1): 
          # save the solution if it is new
          t = tuple(sorted((die(p1), die(p2))))
          if t not in sol:
            sol += [t]
            yield t

# the number of faces on the dice
faces = int(argv[1]) if len(argv) == 2 else 6
# output any solutions found
for p1, p2 in dice_pairs(faces, same=False):
  print(p1, '|', p2)

from sys import argv

from itertools import combinations

from functools import reduce

from operator import mul

from number_theory import factors, divisors

from polynomial import Poly

# generate cyclotomic polynomials

def cyclotomic(n):

# phi(1)

phi = Poly([-1, 1])

if n == 1:

return phi

# find unique prime factors of n

f = set(factors(n))

# If p is a prime that does not divide m then phi(m.p)[x] =

# phi(m)[x^p] / phi(m)[x]. So starting with p, the 1st prime

# in f we have phi(1.p)[x] = phi(1)[x^p] / phi(1)[x]. And we

# can then repeat this process for the next prime in f (say

# q) to show that phi(p.q)[x] = phi(p)[x^q] / phi(q)[x]. We

# can continue this for all primes in f.

for p in f:

phi, rem = divmod(phi.compose(Poly([(1, p)])), phi)

# we can now account for any squared component in f using

# the identity phi(n)[x] = phi(q)[x^(n/q)] where q is the

# product of the distinct prime factors of n

return phi.compose(Poly([(1, n // reduce(mul, f, 1))]))

# output the face values of a die specified by polynomial p

def die(p):

d = []

for e, v in enumerate(p.coeff):

d += [e] * v

return tuple(sorted(d))

# generate pairs of dice giving the same results when thrown

# and added as two identical n-faced dice numbered from 1 to

# n (only dice with equal numbers of faces if same is True)

def dice_pairs(n, same=True):

# for saving solutions

sol = []

# holds the cyclotomic polynomial factorisatiosn of the dice

# generating polynomial x + x^2 + ... + x^faces

l_poly = []

for d in divisors(faces):

if d > 1:

l_poly += [cyclotomic(d)]

ln_poly = len(l_poly)

l_p2 = l_poly + l_poly

# now choose the number of polynomial factors for the

# first die

for nf in range(1, ln_poly + 1):

# check all combinations of this number of polynomials

for f in combinations(range(len(l_p2)), nf):

# list the polynomials for the first die

t = [l_p2[i] for i in f]

# multiply them (and x) for the polynomial for the first die

p1 = reduce(mul, t, Poly([0, 1]))

# list the remaining polynomials for the second die

t = [l_p2[i] for i in range(len(l_p2)) if i not in f]

# multiply them (and x) for the polynomial for the second die

p2 = reduce(mul, t, Poly([0, 1]))

# all polynomial coefficients must be non-negative without zeros

if all(x >= 0 for x in p1.coeff + p2.coeff) and p1(0) == p2(0):

# if necessary check that the dice have the same number of faces

if not same or p1(1) == p2(1):

# save the solution if it is new

t = tuple(sorted((die(p1), die(p2))))

if t not in sol:

sol += [t]

yield t

# the number of faces on the dice

faces = int(argv[1]) if len(argv) == 2 else 6

# output any solutions found

for p1, p2 in dice_pairs(faces, same=False):

print(p1, '|', p2)

This code uses my number theory and polynomial libraries.

Sunday Times Teaser 2739 – Funny Dice

by Michael Fletcher

Published: 22 March 2015 (link)

Leave a comment to Peter Hayes Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta