Brain-Teaser 790: Multi-value coil
From The Sunday Times, 5th September 1976 [link]
Post Office multi-value coil machines are designed to vend strips of five stamps. Soon after the introduction of the 8½p and 6½p first and second class postal rates the machines sold for 10p a strip of stamps values 6p, 1p, ½p, 2p and ½p respectively (as always with these machines the last stamp being the lowest in case of tearing). While catering for both rates it was impossible to make up either 6½p or 8½p with a joined strip of stamps.
However an efficiency expert worked out a possible 10p strip which afforded the following:
(i) from one strip either first or second rate in a joined strip;
(ii) from two joined strips, three second class rates, each in a joined strip;
(iii) from three joined strips, two first class rates plus two second class rates, each in a joined strip.Of course the “expert” assumed that all ½p steps from ½p to 10p were available in stamps.
What was his suggested strip?
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.
[teaser790]
S2T2 
Jim Randell 9:56 am on 29 June 2021 Permalink |
Working in units of half-pennies we can keep amounts in integers.
The value of one complete strip is 20 (= 10p), the first class rate is 17 (= 8.5p), and the second class rate is 13 (= 6.5p).
This Python 3 program runs in 82ms.
Run: [ @replit ]
from enigma import irange, subsets, printf # decompose total <t> into <k> positive integers def decompose(t, k, ns=[]): if k == 1: yield ns + [t] else: k -= 1 for n in irange(1, t - k): yield from decompose(t - n, k, ns + [n]) # can values in <vs> be made from segments of <ss> def _connected(vs, ss): # are we done? if not vs: return True else: v = vs[0] ss = list(x for x in ss if x) # drop empty lists # consider segments for (i, ns) in enumerate(ss): if sum(ns) < v: continue # shortcut # and sub-segments for (j, k) in subsets(irange(0, len(ns)), size=2): if sum(ns[j:k]) == v: if _connected(vs[1:], ss[:i] + ss[i + 1:] + [ns[:j], ns[k:]]): return True return False connected = lambda vs, ns: _connected(vs, [ns]) # check a sequence def check(ns): # (i) 13 and 17 can be made from 1 strip if not(connected([13], ns) and connected([17], ns)): return False # (ii) three lots of 13 from 2 joined strips if not(connected([13] * 3, ns * 2)): return False # (iii) two lots of 13 _and_ two lots of 17 from 3 joined strips if not(connected([13, 17] * 2, ns * 3)): return False # passed return True # look for viable strips for ns in decompose(20, 5): # lowest value stamp comes last if ns[-1] == min(ns) and check(ns): # output solution printf("strip = {ns}")Solution: The stamps on the suggested strip were: 1½p, 1½p, 3½p, 3p, ½p.
LikeLike