Sunday Times Teaser 2846 – Bingo!

by Mike Fletcher

Published April 9 2017 (link)

The infant teacher played a bingo game with his class. He had two identical dice, the numbers on the six faces of each being 1, 2, 2, 3, 3 and 3. He told the class that he would throw the pair of dice, add up the two numbers showing, and call that number out in a game of bingo. He then asked each member of the class to make their own bingo card consisting of five numbers of their own choice. He explained that they could repeat a number on their card if they wished (and then delete just one occurrence of the number whenever it was called). Most of the class chose the five possible different totals as their bingo numbers, but one very clever girl chose the best possible selection.

What were her five numbers?

5 Comments Leave one →

Brian Gladman permalink

My initial thought was that the card would have the most probable number on it five times. But, remembering Mike Fletcher’s earlier dice puzzles, I suspected that the puzzle was more subtle and this was confirmed by Peter Hayes (in a private communication) soon after the teaser was published.

We can calculate the probabilities of all the different sequences of five dice throws as follows:


from itertools import combinations_with_replacement as cwr, product
from collections import Counter, defaultdict
from fractions import Fraction as RF
from functools import reduce
from math import factorial

# the number of numbers on each card
nos_on_card = 5

# return the product of a sequence of values
prod = lambda seq: reduce(lambda x, y: x * y, seq, 1)

# count the times each sum of the two dice occurs
cnt = defaultdict(int)
for a, b in product((1, 2, 2, 3, 3, 3), repeat=2):
  cnt[a + b] += 1

# calculate the probability of each sequence of five values
cp = []
# choose five numbers from those that can be thrown
for c in cwr(sorted(cnt.keys()), nos_on_card):
  # find the probability of this sequence of throws
  # when in any specified order
  pr = prod((RF(cnt[n], 36) for n in c))
  
  # now find out how often it occurs in any order
  fr = factorial(nos_on_card)
  for t in Counter(c).values():
    fr //= factorial(t)
  # and hence the total probability of the sequence
  cp.append((pr * fr, c))

# output cards, probabilities and frequencies in 
# decreasing order
cp.sort(reverse=True)
nrm = cp[-1][0].denominator
for p, c in cp:
  print(f'{c} ==> {p} ({nrm * p})')

from itertools import combinations_with_replacement as cwr, product

from collections import Counter, defaultdict

from fractions import Fraction as RF

from functools import reduce

from math import factorial

# the number of numbers on each card

nos_on_card = 5

# return the product of a sequence of values

prod = lambda seq: reduce(lambda x, y: x * y, seq, 1)

# count the times each sum of the two dice occurs

cnt = defaultdict(int)

for a, b in product((1, 2, 2, 3, 3, 3), repeat=2):

cnt[a + b] += 1

# calculate the probability of each sequence of five values

cp = []

# choose five numbers from those that can be thrown

for c in cwr(sorted(cnt.keys()), nos_on_card):

# find the probability of this sequence of throws

# when in any specified order

pr = prod((RF(cnt[n], 36) for n in c))

# now find out how often it occurs in any order

fr = factorial(nos_on_card)

for t in Counter(c).values():

fr //= factorial(t)

# and hence the total probability of the sequence

cp.append((pr * fr, c))

# output cards, probabilities and frequencies in

# decreasing order

cp.sort(reverse=True)

nrm = cp[-1][0].denominator

for p, c in cp:

print(f'{c} ==> {p} ({nrm * p})')

It is also possible to analytically compute the average number of Bingo calls for a win when each card is played in isolation. I thought that this would be really hard but John Crabtree explained how to do this for one set of numbers (thanks John!) and I was then able to do this for all 126 cards as follows:


from itertools import combinations_with_replacement, permutations, product
from collections import defaultdict
from fractions import Fraction as RF
from functools import reduce

# the number of numbers on each card
nos_on_card = 5

# return the product of a sequence of values
prod = lambda seq: reduce(lambda x, y: x * y, seq, 1)

# return the distinct permutations of a seqence 
def distinct_permutations(x):
  seen = set()
  for p in permutations(x):
    if p not in seen:
      seen.add(p)
      yield p
  
# count the times each sum of the two dice occurs
cnt = defaultdict(int)
for a, b in product((1, 2, 2, 3, 3, 3), repeat=2):
  cnt[a + b] += 1

# for each card, compute the expected number of calls for a Bingo win
# when played in isolation
cp = []
# choose five numbers for the card from those that can be thrown
for c in combinations_with_replacement(sorted(cnt.keys()), nos_on_card):
  # compute the probability of this sequence of throws
  pr = prod((RF(cnt[n], 36) for n in c))

  # compute and sum the expectation values for each sequence of throws
  # that give this card a win
  total_exp = 0
  for p in distinct_permutations(c):
    # for each step in this sequence, calculate the probability that one
    # of the numbers we still need will be thrown - the expectation for
    # this event is the inverse of this probability and that for the
    # sequence as a whole is the sum of these inverse probabilities
    event_pr = [RF(sum(cnt[n] for n in set(p[i:])), 36) for i in range(len(c))]
    # the overall expectation for the sequence on the card is the sum
    # of the expectations for each sequence of throws matching the card
    # multiplied by its conditional probability given that the card will
    # be matched (that is the relative probability contribution of this
    # sequence of calls compared to that of all other sequences that
    # match the card)
    total_exp += sum(1 / x for x in event_pr) * (pr / prod(event_pr))
  cp.append((total_exp, c))

# output cards and the expected number of calls for a win in best
# to worst order
for p, c in sorted(cp):
  print(f'{c} ==> {float(p):10.6f} ({p.numerator:,}/{p.denominator:,})')

from itertools import combinations_with_replacement, permutations, product

from collections import defaultdict

from fractions import Fraction as RF

from functools import reduce

# the number of numbers on each card

nos_on_card = 5

# return the product of a sequence of values

prod = lambda seq: reduce(lambda x, y: x * y, seq, 1)

# return the distinct permutations of a seqence

def distinct_permutations(x):

seen = set()

for p in permutations(x):

if p not in seen:

seen.add(p)

yield p

# count the times each sum of the two dice occurs

cnt = defaultdict(int)

for a, b in product((1, 2, 2, 3, 3, 3), repeat=2):

cnt[a + b] += 1

# for each card, compute the expected number of calls for a Bingo win

# when played in isolation

cp = []

# choose five numbers for the card from those that can be thrown

for c in combinations_with_replacement(sorted(cnt.keys()), nos_on_card):

# compute the probability of this sequence of throws

pr = prod((RF(cnt[n], 36) for n in c))

# compute and sum the expectation values for each sequence of throws

# that give this card a win

total_exp = 0

for p in distinct_permutations(c):

# for each step in this sequence, calculate the probability that one

# of the numbers we still need will be thrown - the expectation for

# this event is the inverse of this probability and that for the

# sequence as a whole is the sum of these inverse probabilities

event_pr = [RF(sum(cnt[n] for n in set(p[i:])), 36) for i in range(len(c))]

# the overall expectation for the sequence on the card is the sum

# of the expectations for each sequence of throws matching the card

# multiplied by its conditional probability given that the card will

# be matched (that is the relative probability contribution of this

# sequence of calls compared to that of all other sequences that

# match the card)

total_exp += sum(1 / x for x in event_pr) * (pr / prod(event_pr))

cp.append((total_exp, c))

# output cards and the expected number of calls for a win in best

# to worst order

for p, c in sorted(cp):

print(f'{c} ==> {float(p):10.6f} ({p.numerator:,}/{p.denominator:,})')

As an alternative, the following program runs a large number of random Bingo trials for each possible card to find the one that wins with the fewest calls on average:


from itertools import combinations_with_replacement as cwr
from random import randrange
from sys import argv

# increase this for more accurate results
trials = 1000 if len(argv) != 2 else int(argv[1])

# the number of numbers on each card
nos_on_card = 5

# run <n> trials for a card <card>
def trial(card, n):
  # the numbers on the die
  die = (1, 2, 2, 3, 3, 3)
  # for the average number of calls for a win
  tot = 0
  # run <n> trials
  for t in range(n):
    # count dice throws while the card is not empty
    crd, cnt = list(card), 0
    while crd:
      # throw the dice
      t = die[randrange(6)] + die[randrange(6)]
      # remove a number if it is on the card
      if t in crd:
        crd.remove(t)
      cnt += 1
    tot += cnt
  return tot / n

# calculate the average number of Bingo calls for a
# win with each possible card
cp = []
for c in cwr((2, 3, 4, 5, 6), nos_on_card):
  t = trial(c, trials)
  cp.append((t, c))

# sort to put winning cards first
cp.sort()
for p, c in cp:
  print(f'{c} ==> {p:7.3f}')

print(f'Her card was {cp[0][1]}, winning on average in {cp[0][0]:2.1f} throws.')

from itertools import combinations_with_replacement as cwr

from random import randrange

from sys import argv

# increase this for more accurate results

trials = 1000 if len(argv) != 2 else int(argv[1])

# the number of numbers on each card

nos_on_card = 5

# run <n> trials for a card <card>

def trial(card, n):

# the numbers on the die

die = (1, 2, 2, 3, 3, 3)

# for the average number of calls for a win

tot = 0

# run <n> trials

for t in range(n):

# count dice throws while the card is not empty

crd, cnt = list(card), 0

while crd:

# throw the dice

t = die[randrange(6)] + die[randrange(6)]

# remove a number if it is on the card

if t in crd:

crd.remove(t)

cnt += 1

tot += cnt

return tot / n

# calculate the average number of Bingo calls for a

# win with each possible card

cp = []

for c in cwr((2, 3, 4, 5, 6), nos_on_card):

t = trial(c, trials)

cp.append((t, c))

# sort to put winning cards first

cp.sort()

for p, c in cp:

print(f'{c} ==> {p:7.3f}')

print(f'Her card was {cp[0][1]}, winning on average in {cp[0][0]:2.1f} throws.')

Congratulations to Mike Fletcher on producing a Teaser for which the ‘obvious’ solution turns out to be wrong! For many solvers, myself included, it was easy to conclude that the best card would be one that would have the most probable dice result repeated five times. It hence comes as some surprise to find that this is far from the best. The reason is most easily explained by considering a simplified game with Bingo cards having only two numbers.

A card with two fives on it will have a probability of being called of (1/3) x (1/3), which is 1/9. A card with a five and a four will win when a five is called (1/3) and then a four (5/18), giving a probability of 5/54, which is lower than 1/9 (5/45). But it will also win when a four is called followed by a five, which, with the same probability, gives an overall probability of 5/27, much larger than 1/9 (3/27).

The point here is that if you put all fives on your card, there is only one sequence of numbers that gets you to Bingo; but if you put a mixture of numbers on your card there are then several sequences of calls, all of which will get you there. And although each specific sequence is less likely to win than the all fives sequence, the fact that there are a number of them more than compensates for this.

Arthur Vause permalink

I had to code this one to verify the counterintuitive result:


from itertools import product
from collections import defaultdict
import operator

counts = defaultdict(int)

die = (1,2,2,3,3,3)

totals = [ d1+d2 for d1 in die for d2 in die]

twodicecounts = defaultdict(int)
for x in totals:
  twodicecounts[x]+=1

for x in twodicecounts:
  print x, twodicecounts[x]

for x in product([x for x in twodicecounts],repeat=5):
  y = list(x)
  y.sort()
  counts[ tuple(y) ] += reduce(operator.mul, [twodicecounts[n] for n in y], 1)

frequencies = [ (counts[y],y) for y in counts ]
frequencies.sort(reverse=True)

print "top ten frequencies:"
for (n,x) in frequencies[:10]:
  print x, n

allfives = (5,5,5,5,5)
print " frequency for", allfives, "=", counts[allfives]

from itertools import product

from collections import defaultdict

import operator

counts = defaultdict(int)

die = (1,2,2,3,3,3)

totals = [ d1+d2 for d1 in die for d2 in die]

twodicecounts = defaultdict(int)

for x in totals:

twodicecounts[x]+=1

for x in twodicecounts:

print x, twodicecounts[x]

for x in product([x for x in twodicecounts],repeat=5):

y = list(x)

y.sort()

counts[ tuple(y) ] += reduce(operator.mul, [twodicecounts[n] for n in y], 1)

frequencies = [ (counts[y],y) for y in counts ]

frequencies.sort(reverse=True)

print "top ten frequencies:"

for (n,x) in frequencies[:10]:

print x, n

allfives = (5,5,5,5,5)

print " frequency for", allfives, "=", counts[allfives]

Brian Gladman permalink

Its nice to find that Arthur’s code and my own produce consistent probability and frequency results. For those who prefer it, here is the equivalent of Arthur’s code in Python 3:


from itertools import product
from collections import defaultdict
from functools import reduce
from operator import mul

# compute the results and the result counts for throwing the two dice
die = (1, 2, 2, 3, 3, 3)
totals = [d1 + d2 for d1 in die for d2 in die]
dicecounts = {x:totals.count(x) for x in set(totals)}

print("two dice frequencies:")
for x in dicecounts:
  print(x, dicecounts[x])

# consider five dice results in sequence and compile the frequency
# of occurrence for each set of five numbers that occurs
counts = defaultdict(int)
for x in product(dicecounts.keys(), repeat=5):
  counts[tuple(sorted(x))] += reduce(mul, (dicecounts[n] for n in x), 1)

# sort the results in order of frequency, highest first 
frequencies = sorted(((counts[x], x) for x in counts), reverse=True)

print("top ten frequencies:")
for (n, x) in frequencies[:10]:
  print(x, n)
print("'all fives' frequency:")
allfives = (5, 5, 5, 5, 5)
print(f'{allfives} {counts[allfives]:7d}')

from itertools import product

from collections import defaultdict

from functools import reduce

from operator import mul

# compute the results and the result counts for throwing the two dice

die = (1, 2, 2, 3, 3, 3)

totals = [d1 + d2 for d1 in die for d2 in die]

dicecounts = {x:totals.count(x) for x in set(totals)}

print("two dice frequencies:")

for x in dicecounts:

print(x, dicecounts[x])

# consider five dice results in sequence and compile the frequency

# of occurrence for each set of five numbers that occurs

counts = defaultdict(int)

for x in product(dicecounts.keys(), repeat=5):

counts[tuple(sorted(x))] += reduce(mul, (dicecounts[n] for n in x), 1)

# sort the results in order of frequency, highest first

frequencies = sorted(((counts[x], x) for x in counts), reverse=True)

print("top ten frequencies:")

for (n, x) in frequencies[:10]:

print(x, n)

print("'all fives' frequency:")

allfives = (5, 5, 5, 5, 5)

print(f'{allfives} {counts[allfives]:7d}')

Richard permalink

It does seem very counter-intuitive, as surely each call is statistically independent. I guess the point is that in early calls there is benefit to having more than one way of ticking a number on my card. So if my card has {2,3,4,5,6} in the more extreme case, I’ll be guaranteed to score on the first call and will reduce my card to 4 spaces.

Reply
- Brian Gladman permalink
  
  Yes, we can see how this works by considering a card with just two numbers. If we put two 5’s on it there is only one sequence of calls that will win – (5, 5) . But if we put a 3 and a 4 on the card, we then win with two sequences of calls – (3, 4) and (4,3) – and while each is less likely than (5, 5) the fact that there are two winning sequences more than compensates for this.
  
  Reply

Sunday Times Teaser 2846 – Bingo!

by Mike Fletcher

Published April 9 2017 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta