New Scientist Back Page Puzzle 24 – Three Stamps
by David Bodycombe
From New Scientist #3250, 5th October 2019
I’m on holiday in the lovely country of Philitaly, and planning to send plenty of postcards because postage is very cheap. But the country only allows up to three stamps on any letter.
Can you tell me which three denominations of stamps would allow me me to cover any cost of postage from 1 cent to 15 cents inclusive?
And which four stamp denominations would allow all values from 1 to 24 cents?
One Comment
Leave one →
-
Brian Gladman permalink12345678910111213141516171819202122232425262728293031from itertools import combinations, combinations_with_replacement, count# find <nv> coin denominations that can make all# amounts from 1 to <tv> using at most <nc> coinsdef find_coinset(nv, tv, nc):# the set of amounts that must be possibletset = set(range(1, tv + 1))# progressively increase the maximum coin value until# we find a solutionfor max_coin in count(nv):# choose <nv> coins from the range 1..max_coinfor c in combinations(range(1, max_coin + 1), nv):# find the amounts that can be made using a maximum# of <nc> coins from this set of coins where each# coin can be chosen multiple timessetv = set().union((sum(cc) for i in range(1, nc + 1)for cc in combinations_with_replacement(c, i)))# success if we can make all amounts from 1 to tvif not tset.difference(setv):return cfor nv, tv, nc in ((3, 15, 3), (4, 24, 3)):cset = find_coinset(nv, tv, nc)print(f"denominations {cset} cover 1..{tv} using {nc} coins.")