Sunday Times Teaser 2578 – The Right Money
by Robin Nayler
Published: 19 February 2012 (link)
In order to conserve his change, Andrew, our local shopkeeper, likes to be given the exact money. So today I went to Andrew’s shop with a collection of coins totalling a whole number of pounds in value. I could use these coins to pay exactly any amount from one penny up to the total value of the coins. Furthermore, the number of coins equalled the number of pounds that all the coins were worth; I had chosen the minimum number of coins to have this property.
(a) How many coins did I have? (b) For which denominations did I have more than one coin of that value?
One Comment
Leave one →
-
Brian Gladman permalink123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778# -*- coding: utf8 -*-from itertools import product, combinations, count# the coins in common circulation in the UK (in pence)uk_coins = (1, 2, 5, 10, 20, 50, 100, 200)# For the 50p, £1 and £2 coins, we can make any value in# multiples of 50p with one 50p, one £1 and any number# of £2 coins. So we only need to consider how to make# values less than 50p.# Generate combinations of the coins in 'coins' that make# the amount 'amount', with a total number of coins not# more than 'tlim' (unless it is 0). If 'coins' does not# contain duplicate values and 'nlim' is greater than zero# then limit the number of coins of any one value to not# more than 'nlim'; if 'coins' contains duplicates and 'nlim'# is not zero, limit coin numbers to the numbers in 'coins'.def make(amount, vals, coins, tlim=0, nlim=0):# have we reached the limit for the number of coins?if nlim:for v in set(vals):nv = coins.count(v)if vals.count(v) > (nlim if nv == 1 else nv):return# have we finished?if amount == 0:yield vals# can we add more coins (if there is a limit on the number)elif not tlim or len(vals) < tlim:# add another coinfor c in coins:# if it is not greater than the amount left and not less# than those already usedif c <= amount and (not vals or c >= vals[-1]):yield from make(amount - c, vals + [c], coins, tlim, nlim)# return true if a given set of coins can make all values# less than 'max_amount'; otherwise return falsedef test(set_c, max_amount):for amount in range(1, max_amount):#for r in make(amount, [], set_c, nlim=1):# we can make this amountbreakelse:# the amount cannot be madereturn Falsereturn True# find the minimum number of coins for making values up# to 50p with coins totalling 50p (using up to eight# coins with at most four of each value)min_len, min_set = None, []# find sets of coins that add up to 50pfor set_coins in make(50, [], uk_coins[:-3], 8, 4):# test that this set can make all values less than 50pif test(set_coins, 50):# keep the set with the fewest number of coinsif not min_len or len(set_coins) < min_len:min_len = len(set_coins)min_set = set_coins# now add a 50p, a £1 and a number of £2 coins to make the# total value in £ equal to the number of coinsn_other = len(min_set) + 2n_two = n_other - (sum(min_set) + 150) // 100print('(a) The number of coins is {}.'.format(n_other + n_two))# accumulate denominations with more than one coinm = ( [x for x in sorted(set(min_set)) if min_set.count(x) > 1]+ [200] if n_two > 1 else [] )s, _, e = ', '.join((str(x) + 'p' if x < 100else u'xa3' + str(x // 100)) for x in m).rpartition(', ')print('(b) More than one of {}.'.format(' and '.join((s, e))))