Problem of the Month (April 2003)

The postal service of the rebuilt Iraq wants to issue 5 denominations of stamps (in whole numbers of dinars) so that by using no more than 3 stamps on an envelope, citizens can pay for any postage from 1 dinar to 36 dinars. How can this be done?

More generally, if they want to to issue d denominations of stamps so that by using no more than s stamps on an envelope, citizens can pay for any postage up to some maximum amount, what should the denominations be, and what is the maximum amount?


ANSWERS

Berend Jan van der Zwaag thought this was an old problem, and indeed it is. I found a thread on a newgroup that was many years old. At that time, Jim Ferry posted the most complete results.

Joseph DeVincentis was the first to find the solution to my first problem: you can do from 1 to 36 dinars using the denominations {1,4,6,14,15}. Gerben Dirksen found yet another solution: {-6,4,9,11,12}. He says sales of these stamps will be "interesting". He also solved some of the other problems.

And special thanks to Trevor Green for the humorous subject line: "Dinar's on me tonight"

Define N(d,s) to be the maximum value of N so that up to s stamps of d denominations can be used to get 1 dinar through N dinars. Define S(d,s) to be the optimal stamp denominations.

Jeremy Galvagni, Joseph DeVincentis, Trevor Green, Sasha Ravsky, and Jim Ferry found that N(1,s)=s with S(1,s)={1}, and N(d,1)=d, and S(d,1)={1,2,3,...d}. They also showed that N(2,s)=(s2+6s+1)/4 with S(2,s)={1,(s+3)/2}.

Joseph DeVincentis showed that N(3,s)≥s(s+2) using S={1,s+1,s+2}, but this is not even optimal for n=4. Jeremy Galvagni also made some conjectures about N(3,s). Sasha Ravsky calculated N(3,s) for s≤64. and N(4,s) for s≤21.

Trevor Green gave the bound N(d,2)≥(d2 - a2)/4 + 2d, where -2≤a≤2 and a=d (mod 4). This construction uses S={1, 2, 3, ... , k-2, k-1, 2k-1, ... , (n-1)k-1, (n-1)k, (n-1)k+1, ..., nk-2}, where d+1 = 4(k-1) + a + 1 and n = 2k + a.

Jim Ferry noticed that with the exception of d=10, S(d,2) is always symmetric, and wondered whether this continues to occur. Philippe Fondanaiche conjectured that for d>3, N(d,s+1)>N(d+1,s).

Trevor Green gave the obvious bound N(d,s)≤(d+1)s, and the less obvious bound N(d,s)≤(s+1)d. He also proved N(d,3)≤(d3 + 18d2 + 23d)/6. Boris Bukh found that Hofmeister proved that N(3,s)=4s3/81 + 2s2/3 + O(s) in the article "A postage stamp problem" (R. Alter and J. A. Barnett, Amer. Math. Monthly, 87 (1980), 206-210).

Boris Bukh sends that if s is fixed and d is large, then this problem reduces to the classical problem of finding thin additive bases of order s. The error term introduced by allowing to have less than s summands is obviously O(d^{s-1}), and so doesn't affect the asymptotics below. It is known that in this case c1(s) N(d,s)1/s≤d≤c2(s) N(d,s)1/s. He says that in "Sequences'' by Halberstam and Roth (1st ed. 1966, pages 35-37) there are even better bounds.

Boris Bukh also considered the case when d is fixed and s is large. In this case a good lower bound is obtained by taking the denominations to be 1, t, t^2, ..., t^{d-1} where t=s/d, which shows N(d,s)≥(1+O(1/s))(s/d)d. He believes that this is sharp, but hasn't proved it yet.

Trevor Green noted that if N(d,s) = N-1, then m(2d,2s)≥N2-1, using S(d,s) and N*S(d,s). Extending this argument shows that if d and s grow at the same rate, N(d,s) grows exponentially.

Here are the results known, most of which came from Jim Ferry and Sasha Ravsky. Joseph DeVincentis sent me more than half of these results, which he found by hand! Philippe Fondanaiche also sent many solutions, not all of which were optimal. Jean-Charles Meyrignac sent me the middle of the third column. Herbert Kociemba improved one of these entries.

Richard Mathar sent me a reference published by Svein Mossige in the "Mathematics of Computation" 36 (April 1981) pages 575-582. This gives the answers for some of the entries for d=4 and d=5.

In 2010, this problem was used as the Son of Darts contest at Al Zimmerman's Programming Contests.

d \ s12345678910 11121314151617181920
112345678910 11121314151617181920
224710141823283440 47546270798898108119130
338152635526989112146 172212259302354418476548633714
4412244471114165234326427 5477088731094138316501935230427823324
5516367012621634551279710551475 20472659340344225629686586691083512903
662052108211388664104516172510 360751187066974812793170612234228874356045745
772670162336638113720013191504778201156817178
883293228524100719113485
99401213107261545
10104615442210162287
1111541865501393
1212642257001871
1313722718782494
14148032310793196
15159238513444063
161610445016065113
171711651519446511
181812860623377949
191914068427669865
2020152788319511589
21211648653668
22221809774251
232319610914923
242421212015631
2525?13616429

Many rows and columns of this table (and the table itself) form sequences in the On-Line Encyclopedia of Integer Sequences. You should also inform them of any extensions.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 6/21/10.