Briefmarkenproblem

Das Briefmarkenproblem ist ein Problem der Kombinatorik und additiven Zahlentheorie. Seien ${\displaystyle k}$ Briefmarken mit Werten ${\displaystyle a_{i}}$ gegeben. Dann wird nach der kleinsten Zahl gefragt, die nicht als Summe von höchstens ${\displaystyle h}$ Briefmarken aus dieser Menge dargestellt werden kann (da nur ${\displaystyle h}$ Marken auf den Briefumschlag passen). Dabei können die Briefmarken auch mehrfach verwendet werden. Das Problem ist im Allgemeinen offen.

Damit verwandt ist das Münzproblem (Frobenius-Problem). Dort gibt es allerdings keine Beschränkung durch ${\displaystyle h}$.

Das Problem geht mindestens bis auf Hans Rohrbach (1937) zurück.

1. ↑ Guy, Unsolved problems in number theory, S. 123.