Eurozahlen/Eindeutige Darstellung/Charakterisierung/Fakt/Beweis

Beweis

Wir zeigen zuerst, dass jede minimale Darstellung von ${}w$ die in (2) angegebenen Koeffizientenbedingungen erfüllt. Es sei also

${}w=a_{1}\cdot 1+a_{2}\cdot 2+a_{3}\cdot 5+a_{4}\cdot 10+a_{5}\cdot 20+a_{6}\cdot 50+a_{7}\cdot 100+a_{8}\cdot 200+a_{9}\cdot 500\,$

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

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

${}{\begin{aligned}w&=a_{1}\cdot 1+a_{2}\cdot 2+a_{3}\cdot 5+a_{4}\cdot 10+a_{5}\cdot 20+a_{6}\cdot 50+a_{7}\cdot 100+a_{8}\cdot 200+a_{9}\cdot 500\\&=b_{1}\cdot 1+b_{2}\cdot 2+b_{3}\cdot 5+b_{4}\cdot 10+b_{5}\cdot 20+b_{6}\cdot 50+b_{7}\cdot 100+b_{8}\cdot 200+b_{9}\cdot 500\end{aligned}}$

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

${}a_{i}=b_{i}\,$

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

${}{\begin{aligned}(a_{1}\cdot 1+a_{2}\cdot 2+a_{3}\cdot 5)+(a_{4}\cdot 10+a_{5}\cdot 20+a_{6}\cdot 50)+(a_{7}\cdot 100+a_{8}\cdot 200)&<10+90+400\\&=500.\end{aligned}}$

Daher kann ${}b_{9}$ nicht größergleich ${}1$ sein und ist ebenfalls ${}0$. So zeigt man absteigend, dass alle Koeffizienten ${}0$ 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