Another Postage Stamp Problem
Chris J. Mitchell · The Computer Journal · 1989
The postage stamp problem requires the selection of a set of k postage stamp denominations such that sums of h (or fewer) of these denominations can realise all the numbers 1,2,…,n for n as large as possible (given k). In this paper we consider a natural analogue of this problem to the case where each stamp denomination is allowed to occur a negative number of times, so long as the sum of the absolute values of the numbers of occurrences is at most h. Interestingly, for the case h=2, the problem considered here is also an analogue of the Golomb Ruler problem. For the case h=2, constructions are shown which give a lower bound on the maximum n achievable.