An envelope holds at most h stamps.
combinatorics/coinage/postage.stamps New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
An envelope holds at most h stamps. For each h and each number k of stamp denominations, which k denominations let you make every postage from 1 up to the largest possible n? [ Editor: problem statement reconstructed from the posting, a table of results offered as "independent confirmation" in a thread titled "5 Math Puzzles"; the original question is not in the collected material. ]
Show solution
[ Editor: each line reads "h, n: denominations": with at most h stamps the listed denominations make every value from 1 to n. For example, with at most 2 stamps of values 1 and 3 one makes 1, 2=1+1, 3 and 4=1+3, but not 5, so "2, 4: 1 3". Several lines with the same h and n are alternative optimal sets. ] -------- 2 stamps, 1 to 10 denominations -------- 2, 2: 1 2, 4: 1 2 2, 4: 1 3 2, 8: 1 3 4 2, 12: 1 3 5 6 2, 16: 1 3 5 7 8 2, 20: 1 2 5 8 9 10 2, 20: 1 3 4 8 9 11 2, 20: 1 3 4 9 11 16 2, 20: 1 3 5 6 13 14 2, 20: 1 3 5 7 9 10 2, 26: 1 2 5 8 11 12 13 2, 26: 1 3 4 9 10 12 13 2, 26: 1 3 5 7 8 17 18 2, 32: 1 2 5 8 11 14 15 16 2, 32: 1 3 5 7 9 10 21 22 2, 40: 1 3 4 9 11 16 17 19 20 2, 46: 1 2 3 7 11 15 19 21 22 24 2, 46: 1 2 5 7 11 15 19 21 22 24 -------- 3 stamps, 1 to 9 denominations --------- 3, 3: 1 3, 7: 1 3 3, 15: 1 4 5 3, 24: 1 4 7 8 3, 36: 1 4 6 14 15 3, 52: 1 3 7 9 19 24 3, 52: 1 4 6 14 17 29 3, 70: 1 4 5 15 18 27 34 3, 93: 1 3 6 10 24 26 39 41 3,121: 1 3 8 9 14 32 36 51 53 -------- 4 stamps, 1 to 8 denominations --------- 4, 4: 1 4, 10: 1 3 4, 10: 1 4 4, 26: 1 5 8 4, 44: 1 3 11 18 4, 70: 1 3 11 15 32 4,108: 1 4 9 16 38 49 4,108: 1 5 8 27 29 44 4,162: 1 4 9 24 35 49 51 4,162: 1 4 10 15 37 50 71 4,162: 1 5 8 25 31 52 71 4,228: 1 3 8 19 33 39 92 102 -------- 5 stamps, 1 to 7 denominations --------- 5, 5: 1 5, 14: 1 4 5, 35: 1 6 7 5, 71: 1 4 12 21 5, 71: 1 5 12 28 5,126: 1 4 9 31 51 5,211: 1 4 13 24 56 61 5,211: 1 5 8 33 54 67 5,336: 1 4 13 24 30 87 106 -------- 6 stamps, 1 to 6 denominations --------- 6, 6: 1 6, 18: 1 4 6, 18: 1 5 6, 52: 1 7 12 6,114: 1 4 19 33 6,216: 1 7 12 43 52 6,388: 1 7 11 48 83 115 -------- 7 stamps, 1 to 5 denominations --------- 7, 7: 1 7, 23: 1 5 7, 69: 1 8 13 7,165: 1 5 24 37 7,345: 1 8 11 64 102 -------- 8 stamps, 1 to 4 denominations --------- 8, 8: 1 8, 28: 1 5 8, 28: 1 6 8, 89: 1 9 14 8,234: 1 6 25 65 -------- 9 stamps, 1 to 3 denominations --------- 9, 9: 1 9, 34: 1 6 9,112: 1 9 20 ------- 10 stamps, 1 to 2 denominations --------- 10, 10: 1 10, 40: 1 6 10, 40: 1 7 -- Jim Ferry <jferry@uiuc.edu> [ Editor: the original question from the thread "5 Math Puzzles" (October 1998), with an answer for h = 3 stamps and n = 70. ] >>>1. The post office wishes to issue a set of stamps >>> (integer denomination) so that with no more than 3 of them, >>> you can pay any postage from 1 cent to 70 cents. What >>> is the minimum number of stamps in the set? >>With 1 2 3 4 9 14 19 43 67 I can get any total up to 90. >> >>Can anyone do better than this? "Chris Nicks" <nickscb@shoneys.com> writes: >I can't believe nobody has posted this yet. >1,2,4,8,16,32,64 >With these seven stamps, I can get any value from $0.01 to $1.27. Perhaps the reason nobody posted it before was because everybody else realized it doesn't work. :-) What you're forgetting is that can only use at most *3* stamps. To pay for 63 cents, you would need 6 stamps in this system. The *UNIQUE* minimal set is .... drum roll please! :-) 1 4 5 15 18 27 34 The minimal number of stamps is 7. Answer found through the use of a computer program. -- Glenn <rhoads@john.rutgers.edu>