Brain-Teaser 774: Postage stamps
From The Sunday Times, 16th May 1976 [link]
I went to the Post Office to buy three 5½p stamps (those were the days!) for my entries for the Brain-teaser, Crossword and Mephisto; but finding a long queue there I bought a 10p book of stamps from a machine, which contained two stamps at each of the following denominations: 2p, 1½p, 1p, ½p. Since I already had four stamps of total value 6½p left over from a similar 10p book I now had just enough stamps for the three entries.
I stuck four of the stamps totalling 5½p on my Brain-teaser entry, but then found that there was room for only three stamps on the Crossword entry (because entrants have to write “Crossword” on the top left-hand corner of the envelope) and the stamps I had left could not be arranged to give me three stamps totalling 5½p for the Crossword entry and five for the Mephisto entry.
What were the denominations of stamps on the Brain-teaser entry?
Current stamp prices in the UK are 85p (1st class) or 66p (2nd class).
This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.
[teaser774]
Frits and 
S2T2 
Jim Randell 10:31 am on 8 June 2021 Permalink |
The following Python program runs in 51ms.
Run: [ @replit ]
# working in half-pence units the denominations avaliable are: # 1 (= .5p), 2 (= 1p), 3 (= 1.5p), 4 (= 2p) from enigma import (multiset, subsets, join, sprintf, printf) # one book of stamps (2 of each denomination) book = multiset.from_seq((1, 2, 3, 4), count=2) # make an amount <t> using <k> stamps from <ss> make = lambda ss, t, k: (s for s in subsets(ss, size=k, select="mC") if sum(s) == t) # there are 4 stamps making 13 (= 6.5p) left over from a book for rs in make(book, 13, 4): # combine these with a new book ss = book.combine(rs) # choose 4 stamps making 11 (= 5.5p) for the Teaser entry for ts in make(ss, 11, 4): # but you can't make 11 (= 5.5p) using 3 stamps from what is left over if any(make(ss.difference(ts), 11, 3)): continue # output solution fmt = lambda xs: join((sprintf("{x:g}p", x=0.5 * x) for x in xs), sep=", ") printf("Teaser = {ts}", ts=fmt(ts))Solution: The stamps used for the Brain-teaser entry were: 1× 1p stamp; 3× 1½p stamps.
The 8 remaining stamps are: 2× ½p; 2× 1p; 4× 2p.
So the correct postage can be made using 4 stamps: 2p + 2p + 1p + ½p.
LikeLike
Frits 12:51 pm on 11 June 2021 Permalink |
Using the same approach as Jim.
2 technical issues:
the decompose function generates duplicates
is there an easier way to determine “remaining” (like a list comprehension)?
# working in half-pence units # decompose <t> into <k> increasing numbers from <ns>, count number <= c # so that sum(<k> numbers) equals <t> def decompose(t, k, ns, s=[], m=1, c=99): if k == 1: if not(t < m) and t in ns: res = s + [t] for x in set(res): if res.count(x) > c: return yield tuple(res) else: for (i, n) in enumerate(ns): if not(n < t): break if not(n < m): yield from decompose(t - n, k - 1, ns[i:], s + [n], n, c) # there are 4 stamps making 13 (= 6.5p) left over from a book leftovers = set(decompose(13, 4, [1, 2, 3, 4] * 2, c=2)) for lo in leftovers: # leftover + 10p book ss = lo + (1, 2, 3, 4) * 2 # choose 4 stamps making 11 (= 5.5p) for the teaser entry for t in set(decompose(11, 4, ss)): remaining = list(ss) for x in t: if x in remaining: remaining.remove(x) # but you can't make 11 (= 5.5p) using 3 stamps from what is left over if any(decompose(11, 3, remaining)): continue print(f"teaser =", f"{', '.join(str(x / 2).rstrip('0').rstrip('.') + 'p' for x in t)}")LikeLike