Maximal zwei Münzen/Eindeutigkeit/Aufgabe/Lösung

Da insbesondere der Betrag ${}1$ beglichen werden kann, muss es eine ${}1$-Riggating-Münze geben. Den Nennbetrag der zweiten Riggating-Münze nennen wir ${}d>1$. Wir behaupten, dass man die Darstellung des Riggating-Preises ${}n$ mit der minimalen Anzahl von Münzen findet, wenn man

${}n=sd+r\,$

mit ${}r$ zwischen ${}0$ und ${}d-1$ berechnet. Die Münzanzahl ist dann ${}s+r$. Die Darstellung kann man erhalten, indem man solange ${}d$-Münzen anhäuft, solange man unterhalb von ${}n$ bleibt, mit der nächsten zusätzlichen ${}d$-Münze wäre man also schon drüber. Was dann noch fehlt füllt man mit ${}1$-Münzen auf. Zum Nachweis der Eindeutigkeit: Es sei

${}n=td+u\,$

eine weitere Darstellung mit

${}t\neq s\,.$

Wir behaupten zunächst

${}t<s\,.$

Denn andernfalls wäre

${}t>s\,,$

also

${}t\geq s+1\,,$

und dann wäre

${}td+u\geq (s+1)d=sd+d>sd+r=n\,,$

das wäre also keine Darstellung von ${}n$.

Für die Anzahl der in der zweiten Darsttellung verwendeten Münzen gilt somit (dafür sei ${}n\neq 1$)

${}t+u=t+n-td=n-t(d-1)>n-s(d-1)=s+n-sd=s+r\,.$

Bei ${}n=1$

ist die Darstellung sowieso eindeutig.

Zur gelösten Aufgabe