Teaser 3328: Loose change
From The Sunday Times, 5th July 2026 [link] [link]
Elaine reminded Phil to take his suit to the dry cleaners. When Phil emptied his pockets he found he had exactly £5 in coins. All denominations of coin were represented (£2, £1, 50p, 20p, 10p, 5p, 2p and 1p) but there were more of one coin than any other.
Phil told all of this to Elaine, but she couldn’t work out how many coins Phil had. “If I told you the total two-figure number of coins you would be able to work out the numbers of each coin present”, said Phil.
Which denomination appeared most and how many of that coin were present?
The S2T2 site now has all puzzles from April 2009 to present (along with solutions), which is a continuous run of the most recent 900 Teaser puzzles. Additionally there are currently 460 older Teaser puzzles available too.
[teaser3328]
Frits, 
Ruud, and 
Alex.T.Sutherland, 
Tony Smith, 
Alex.T.Sutherland, 
John Crabtree are discussing. 
S2T2 
Jim Randell 7:43 am on 5 July 2026 Permalink |
This Python program runs in 87ms. (Internal runtime is 13ms).
from enigma import (express, group, singleton, printf) # denominations (in increasing order) ds = [1, 2, 5, 10, 20, 50, 100, 200] # generate candidate quantities def generate(): # make a total amount of 500p for qs in express(500, ds, min_q=1): # only allow those with a distinct maximum quantity if qs.count(max(qs)) == 1: yield qs # collect arrangements by total number of coins g = group(generate(), by=sum) # look for unique 2-digit totals for (k, vs) in g.items(): if k < 10 or k > 99: continue qs = singleton(vs) if qs is None: continue # output solution printf("{k} coins = {qs} * {ds}p") # find maximum occurring denomination i = qs.index(max(qs)) printf("-> most common = {q} * {d}p", q=qs[i], d=ds[i])Solution: [To Be Revealed]
LikeLike
Ruud 10:55 am on 5 July 2026 Permalink |
import collections coins = (200, 100, 50, 20, 10, 5, 2, 1) def allocate(amount_left, coins_left, result): if coins_left: for n in range(1, amount_left // coins_left[0] + 1): if amount_left >= n * coins_left[0]: yield from allocate(amount_left - n * coins_left[0], coins_left[1:], result + [n]) else: if amount_left == 0 and result.count(max(result)) == 1 and len(str(sum(result))) == 2: yield result collect = collections.defaultdict(list) for coin_count in allocate(500, coins, []): collect[sum(coin_count)].append(coin_count) for number_of_coins, coin_counts in collect.items(): if len(coin_counts) == 1: print(*(f"{number} * {coin}p" for coin, number in zip(coins, coin_counts[0]) if number == max(coin_counts[0]))) print(*(f"{number} * {coin}p" for coin, number in zip(coins, coin_counts[0])))LikeLike
Frits 8:38 pm on 5 July 2026 Permalink |
A two-stage rocket. More efficient than doing only one standard decompose. S =2 seems to be the optimum.
from collections import defaultdict denoms = [1, 2, 5, 10, 20, 50, 100, 200] N = len(denoms) # remaining target starting with 1 coin of each T = 500 - sum(denoms) # determine smallest <S> denominations last (S > 0) S = 2 # decompose: choose numbers from <ns> so that sum(chosen numbers) equals <t> # and increment these numbers with 1 def decompose(t, ns, m, s=[]): if m == 0: n, r = divmod(t, ns[0]) if not r: yield [n + 1] + s[::-1] else: for i in range(t // ns[m] + 1): yield from decompose(t - i * ns[m], ns, m - 1, s + [i + 1]) # decompose: choose numbers from <ns> so that sum(chosen numbers) <= t def decompose_upto(t, ns, m, s=[]): if m < 0: yield s[::-1] else: for i in range(t // ns[m] + 1): yield from decompose_upto(t - i * ns[m], ns, m - 1, s + [i + 1]) # dictionary of total number of coins still to be made d = defaultdict(list) denoms2 = denoms[S:] # all except the <S> smallest denominations sm = sum(denoms2) # get coins for these denominations not exceeding T for p1 in decompose_upto(T, denoms2, N - S - 1): todo = T + sm - sum(x * y for x, y in zip(p1, denoms2)) d[todo] += [p1] # dictionary of total number of coins occurences freqs = defaultdict(list) for k, vs in sorted(d.items()): # we still need to make <k> pennies with the <S> lowest denominations for p2 in decompose(k, denoms[:S], S - 1): for v in vs: if 10 <= (ncoins := sum(coins := p2 + v)) <= 99: # there were more of one coin than any other if coins.count(max(coins)) == 1: freqs[ncoins] += [coins] # if I told you the total two-figure number of coins you would be able to # work out the numbers of each coin present for k, vs in freqs.items(): if len(vs) != 1: continue # denomination that appeared most ans = max([(x, y) for x, y in zip(vs[0], denoms)]) print(f"answer: {ans[1]}p appeared most ({ans[0]} times)")LikeLike