Sunday Times Teaser 2724 – Headcount

by Victor Bryant

A game I play with my grandson has six rounds. In round one, seven coins are tossed, in round two, six, in round three, five, and so on, down to two coins in round six. On each round I then get a number of points equal to the number of heads and my grandson gets a number of points equal to the number of tails. But, before each round, we each predict our score and gain an extra ‘bonus’ of a fixed number of points (less than 40) when our predictions are correct.

In one game we noticed that, at the end of each round, the combined total of our points so far had always been a prime number.

How much is the bonus and what was the sum of our scores at the end of this game?

5 Comments Leave one →

brian gladman permalink


from number_theory import Primes

fs = 'bonus = {}, final points total = {}.'
# possible multiples of the bonus points per round
bpr = (0, 1, 2)

for bonus in range(1, 40):
  for r7 in bpr:
    # total points so far after seven coin round
    s7 = 7 + r7 * bonus
    if s7 in Primes():
      for r6 in bpr:
        # total points so far after the six coin round
        s6 = s7 + 6 + r6 * bonus
        if s6 in Primes():
          for r5 in bpr:
            # total points so far after the five coin round
            s5 = s6 + 5 + r5 * bonus
            if s5 in Primes():
              for r4 in bpr:
                # total points so far after the four coin round
                s4 = s5 + 4 + r4 * bonus
                if s4 in Primes():
                  for r3 in bpr:
                    # total points so far after the three coin round
                    s3 = s4 + 3 + r3 * bonus
                    if s3 in Primes():
                      for r2 in bpr:
                        # total points so far after the two coin round
                        s2 = s3 + 2 + r2 * bonus
                        if s2 in Primes():
                          print(fs.format(bonus, s2))

from number_theory import Primes

fs = 'bonus = {}, final points total = {}.'

# possible multiples of the bonus points per round

bpr = (0, 1, 2)

for bonus in range(1, 40):

for r7 in bpr:

# total points so far after seven coin round

s7 = 7 + r7 * bonus

if s7 in Primes():

for r6 in bpr:

# total points so far after the six coin round

s6 = s7 + 6 + r6 * bonus

if s6 in Primes():

for r5 in bpr:

# total points so far after the five coin round

s5 = s6 + 5 + r5 * bonus

if s5 in Primes():

for r4 in bpr:

# total points so far after the four coin round

s4 = s5 + 4 + r4 * bonus

if s4 in Primes():

for r3 in bpr:

# total points so far after the three coin round

s3 = s4 + 3 + r3 * bonus

if s3 in Primes():

for r2 in bpr:

# total points so far after the two coin round

s2 = s3 + 2 + r2 * bonus

if s2 in Primes():

print(fs.format(bonus, s2))

Here is a slower but more compact solution:


from itertools import product
from number_theory import Primes

# return the cumulative sums of a sequence
def cumulative_sum(x):
  it = iter(x)
  s = next(it)
  yield s
  for c in it:
    s = s + c
    yield s

fs = 'bonus = {}, final points total = {}.'
# the range of the possible bonus 
for bonus in range(1, 40):
  # which is added none, once or twice per round over six rounds
  for p in product((0, 1, 2), repeat=6):
    # calculate the total points awarded in each round
    s = (a + b * bonus for a, b in zip(range(7, 1, -1), p))
    # find the cumulative sums of the round totals
    t = tuple(cumulative_sum(s))
    # which must all be primes
    if all(x in Primes() for x in t):
      print(fs.format(bonus, t[-1]))

from itertools import product

from number_theory import Primes

# return the cumulative sums of a sequence

def cumulative_sum(x):

it = iter(x)

s = next(it)

yield s

for c in it:

s = s + c

yield s

fs = 'bonus = {}, final points total = {}.'

# the range of the possible bonus

for bonus in range(1, 40):

# which is added none, once or twice per round over six rounds

for p in product((0, 1, 2), repeat=6):

# calculate the total points awarded in each round

s = (a + b * bonus for a, b in zip(range(7, 1, -1), p))

# find the cumulative sums of the round totals

t = tuple(cumulative_sum(s))

# which must all be primes

if all(x in Primes() for x in t):

print(fs.format(bonus, t[-1]))

Arthur Vause permalink

Here is my variation. As suspected there are many solutions, but only one with a bonus below 40. Interestingly, for any bonus up to 200000, there is only one possible final total.


plist = [0,0,1]+[1,0]*500000
for n in xrange(3,1000,2):
  if plist[n]: plist[n*n::2*n]= [0]*len(plist[n*n::2*n])
primes=set(x for x in xrange(1000000) if plist[x])

for b in xrange(1,200000):
  runningtotals = [0]
  for c in xrange(7,1,-1):
    runningtotals = [ c+r+b*n for r in runningtotals
                      for n in (0,1,2)
                      if c+r+b*n in primes]
    if len(runningtotals)==0:
      break

  if len(runningtotals)>0:
    print "bonus={0}, final sum of scores can be {1}".format(b, runningtotals)

plist = [0,0,1]+[1,0]*500000

for n in xrange(3,1000,2):

if plist[n]: plist[n*n::2*n]= [0]*len(plist[n*n::2*n])

primes=set(x for x in xrange(1000000) if plist[x])

for b in xrange(1,200000):

runningtotals = [0]

for c in xrange(7,1,-1):

runningtotals = [ c+r+b*n for r in runningtotals

for n in (0,1,2)

if c+r+b*n in primes]

if len(runningtotals)==0:

break

if len(runningtotals)>0:

print "bonus={0}, final sum of scores can be {1}".format(b, runningtotals)

Arthur Vause permalink

In fact there is at most 1 solution for any bonus up to 10,000,000

Reply

brian gladman permalink

I like your solution Arthur so I have slightly recast it and documented it as follows:


from number_theory import Primes

fs = 'bonus = {}, final points total = {}.'
# the range of the possible bounus 
for bonus in range(1, 40):
  # a list of the possible prime totals before each round
  totals = [0]
  # run the six rounds
  for rounds in range(6):
    # a list for the possible prime totals at the end of this round
    new_totals = []
    # go through the totals at the end of the previous round
    for previous in totals:
      # and calculate the possible new prime totals at the end of
      # this round - the bonus can be added 0, 1 or 2 times
      for multiple in range(3):
        current = previous + 7 - rounds + multiple * bonus
        # add any totals that are prime
        if current in Primes():
          new_totals += [current]
      # if there are no prime totals, this bonus value fails 
      if not totals:
        break
    else:
      # update the totals for the next round
      totals = new_totals
  if totals:
    print(fs.format(bonus, *totals))

from number_theory import Primes

fs = 'bonus = {}, final points total = {}.'

# the range of the possible bounus

for bonus in range(1, 40):

# a list of the possible prime totals before each round

totals = [0]

# run the six rounds

for rounds in range(6):

# a list for the possible prime totals at the end of this round

new_totals = []

# go through the totals at the end of the previous round

for previous in totals:

# and calculate the possible new prime totals at the end of

# this round - the bonus can be added 0, 1 or 2 times

for multiple in range(3):

current = previous + 7 - rounds + multiple * bonus

# add any totals that are prime

if current in Primes():

new_totals += [current]

# if there are no prime totals, this bonus value fails

if not totals:

break

else:

# update the totals for the next round

totals = new_totals

if totals:

print(fs.format(bonus, *totals))

Arthur Vause permalink

Thanks for making the solution more understandable – I ought to add comments myself.

I made a couple of minor mods to my original version when checking bonuses up to 10,000,000 :

1. Only consider odd values of bonuses, as the total after the third round, 18 + n*bonus must be prime and therefore must be odd (and n must be 1 or 5)

2. An initial check that either 18 + bonus or 18+5*bonus is prime eliminates many other values of bonus

After applying these mods, the time taken by the program was dominated by generating the set of primes.

Reply

Sunday Times Teaser 2724 – Headcount

by Victor Bryant

Leave a comment to Arthur Vause Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta