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

Aus Wikiversity
Zur Navigation springen Zur Suche springen

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

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

eine weitere Darstellung mit

Wir behaupten zunächst

Denn andernfalls wäre

also

und dann wäre

das wäre also keine Darstellung von .

Für die Anzahl der in der zweiten Darsttellung verwendeten Münzen gilt somit (dafür sei )

Bei ist die Darstellung sowieso eindeutig.
Zur gelösten Aufgabe