×

A note on the postage stamp problem. (English) Zbl 1177.11014

Let \(h,k\) be fixed positive integers, and let \(A\) be any set of positive integers. Let \(hA:=\{a_1+a_2+\cdots+a_r:a_i \in A, r \leq h\}\) denote the set of all integers representable as a sum of no more than \(h\) elements of \(A\), and let \(n(h,A)\) denote the largest integer \(n\) such that \(\{1,2,\ldots,n\} \subseteq hA\). Let \(n(h,k)=\max_A\:n(h,A)\), where the maximum is taken over all sets \(A\) with \(k\) elements. Here the authors determine \(n(h,A)\) when the elements of \(A\) are in arithmetic progression. The following is proved:
Theorem 1: Let \(h, k, d\) be positive integers. Then
\[ n(h, \{1, 1+d, 1+2d, \dots, 1+(k-1)d\}) = h \text{ if }h\leq d-1; and =h+(k-1)(h+1-d)d \text{ if } h\geq d. \]
In particular, they determine the value of \(n(h,2)\) as follows.
Corollary 2: For \(h\geq 1\), \[ n(h,2) =\left\lfloor\frac {h^2+6h+1}{4}\right\rfloor. \] Moreover, the only extremal basis is \(\{1, (h+3)/2\}\) if \(h\) is odd, and \(\{1, (h+2)/2\}\) and \(\{1, (h + 4)/2\}\) if \(h\) is even.

MSC:

11B13 Additive bases, including sumsets

Software:

OEIS
PDFBibTeX XMLCite
Full Text: EuDML EMIS