Münzproblem

Das Münzproblem (auch als Frobenius-Problem bekannt) aus dem Gebiet der Zahlentheorie stellt die Frage, welche natürliche Zahlen sich in der Form ${\displaystyle m=x_{1}a_{1}+x_{2}a_{2}+\dots +x_{n}a_{n}}$ schreiben lassen, wobei ${\displaystyle a_{1}}$ bis ${\displaystyle a_{n}}$ vorgegebene teilerfremde Zahlen sind und die Koeffizienten ${\displaystyle x_{1}}$ bis ${\displaystyle x_{n}}$ als natürliche Zahlen (einschließlich 0) gewählt werden sollen. Genauer wird nach der größten Zahl gefragt, die sich nicht in dieser Form schreiben lässt, sie wird als Frobenius-Zahl bezeichnet.

Das Problem geht auf Ferdinand Georg Frobenius zurück, der Name kommt von der anschaulichen Formulierung der Fragestellung, welche Preise sich mit einem vorgegebenen Satz an Münzen mit den Werten ${\displaystyle a_{1}}$ bis ${\displaystyle a_{n}}$ bezahlen lassen. Den Fall ${\displaystyle n=2}$ konnte James Joseph Sylvester 1884 vollständig lösen, für mehr Zahlen scheint es dagegen keine einfache Formel zu geben.

Verwandt damit ist das Briefmarkenproblem.