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?

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)=(s²+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) ≥ (d²–a²)/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) ≤ (d³ + 18d² + 23d)/6. Boris Bukh found that Hofmeister proved that N(3,s) = 4s³/81 + 2s²/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 c₁(s) N(d,s)^1/s≤d ≤ c₂(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², ..., 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) ≥ N²–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.

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.