A Postage Stamp Problem

Abstract

The postage stamp problem is the following: An envelope may carry no more than h stamps, and one has available k integer-valued stamp denomi-nations. Given h and k, find the maximal integer n = n(h, k) such that all integer postage values from 1 to n can be made up. In addition, find all sets of k stamp denominations satisfying this condition. The problem statement is usually modified by augmenting the solution sets with a stamp of value zero, and requiring that a letter carry exactly h stamps. For example, if h = 2 and k = 3, then n(h, k) = 8. The unique solution set is {0, 1, 3, 4}. A construction of the integers 1,..., 8 is