Sunday Times Teaser 3188 – Royal Mail Slims Down
by Susan Bricket
Published Sunday October 29 2023 (link)
The Royal Mail, facing stiff competition, was looking for ways to streamline and simplify its operations. One dotty idea circulating in 2022 was to sell only two face values of postage stamps. Customers would then need to be able to make up 68p for a second-class letter and all values above 68p, to be ready for subsequent price rises. An obvious solution would be to sell only 1p and 68p stamps. But this would mean sticking 28 stamps on a first-class letter (costing 95p), leaving little room for the address!
Which two stamp values would minimise the total number of stamps required to post two letters, one at 68p and one at 95p, and still allow any value above 68p to be made up?
One Comment
Leave one →
-
BRG permalink1234567891011121314151617181920212223242526272829303132333435363738from math import gcd# with two stamps with values <a> and <b>, return the number of each stamp# that minimises the total number of stamps needed to make the value <v>def solve(a, b, v):min_sm, min_n2 = 100, None# consider the numbers of stamp <a>for na in range(v // a + 1):# find the number of step to make <b>nb, r = divmod(v - na * a, b)if not r:# save the numbers of <a> and <b># stamps that minimise the total# number of stampsif (sm := na + nb) < min_sm:min_sm, min_n2 = sm, (na, nb)return min_n2# for saving the minimum stampsnc_min, nc_ab, nc_sol = 100, None, None# consider the values of the two stamps ...for a in range(2, 69):for b in range(a + 1, 69):# ... which must be co-prime and have a Frobenius number ...if gcd(a, b) == 1:# ... less than 68 in order to make all values above 67if a * b - (a + b) >= 68:breaknc_68, nc_95 = solve(a, b, 68), solve(a, b, 95)# minimise the number of stamps needed to make the two valuesif (nc := sum(nc_68 + nc_95)) < nc_min:nc_min, nc_ab, nc_sol = nc, (a, b), (nc_68, nc_95)(a, b), (x, y) = nc_ab, nc_solprint(f"A minimum of {nc_min} stamps with {a}p and {b}p stamps ({x}, {y}).")
