Eurozahlen/Eindeutige Darstellung/Charakterisierung/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Wir zeigen zuerst, dass jede minimale Darstellung von die in (2) angegebenen Koeffizientenbedingungen erfüllt. Sei also

eine minimale Darstellung. Wenn der Koeffizient vor (also ) größer als wäre, also mindestens , so könnte man zwei -Euromünzen durch eine -Euromünze ersetzen und hätte eine Darstellung mit weniger Summanden im Widerspruch zur Minimalität (ebenso für den Koeffizienten vor und vor ). Wenn der Koeffizient vor größer als wäre, also mindestens , so könnte man zwei -Euroscheine durch einen -Euroschein ersetzen und hätte eine Darstellung mit weniger Summanden im Widerspruch zur Minimalität (ebenso für den Koeffizient vor ). Wenn der Koeffizient vor größer als wäre, also mindestens , so könnte man drei -Euromünzen durch eine -Euromünze und einen -Euroschein ersetzen und hätte eine Darstellung mit weniger Summanden im Widerspruch zur Minimalität (ebenso für den Koeffizienten vor und vor ). Wenn eine -Euromünze doppelt und eine -Euromünze einfach vorkommt, so kann man dies durch einen -Euroschein ersetzen im Widerspruch zur Minimalität der Darstellung, ebenso bei einem doppelten Vorkommen von oder .

Wir zeigen nun die Eindeutigkeit der minimalen Darstellung und nehmen an, dass zwei Zerlegungen

vorliegen. Da beide Darstellungen minimal sind, müssen nach der bisherigen Überlegung die Koeffizienten jeweils die Koeffizientenbedingungen erfüllen. Wir werden zeigen, dass es überhaupt nur eine Darstellung gibt, die die Koeffizientenbedingungen erfüllt. Wir müssen also zeigen, dass

für alle gilt. Wenn für ein bestimmtes die Koeffizienten und beide sind, so kann man beidseitig die zugehörige Eurozahl (eventuell zweimal) abziehen und erhält dann eine kleinere Zahl , für die zwei Darstellungen vorliegen, die die Koeffizientenbedingungen erfüllen. Da man diese Überlegung für jedes durchführen kann, gelangt man zu einer Gleichheit, bei der jeweils mindestens einer der Koeffizienten gleich ist. Es ist dann zu zeigen, dass auch der andere Koeffizient gleich ist. Dies zeigen wir absteigend, beginnend mit bzw. . Da die Situation symmetrisch ist, können wir annehmen, dass ist. Aufgrund der Koeffizientenbedingungen ist (die Klammern sind suggestiv und sollen die verwendeten Abschätzungen verdeutlichen, die erste ist echt)

Daher kann nicht größergleich sein und ist ebenfalls . So zeigt man absteigend, dass alle Koeffizienten sind und dass die Darstellung also eindeutig ist.

Wir zeigen nun die andere Richtung aus Teil (2), dass eine Darstellung mit den gegebenen Koeffizientenbedingungen die eindeutige Darstellung sein muss. Mit der gleichen Argumentation wie eben, angewendet auf eine solche Darstellung und die minimale Darstellung, ergibt sich, dass die Darstellungen übereinstimmen.

Der dritte Teil ergibt sich daraus, dass die entstehende Darstellung die in (2) formulierten Koeffizientenbedingungen erfüllen muss.

Zur bewiesenen Aussage