Eurozahlen/Eindeutige Darstellung/Charakterisierung/Fakt

Satz über die minimale Bargeld-Darstellung

Es gelten die folgenden Aussagen.

1. Jede natürliche Zahl ${}w$ besitzt eine eindeutige Summendarstellung

   ${}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\,$

   (mit $a_{1},\ldots ,a_{9}\in \mathbb {N}$) mit der Eigenschaft, dass die Gesamtanzahl der Summanden (also $a_{1}+a_{2}+\cdots +a_{9}$) unter allen Darstellungen minimal ist.

2. Eine solche Darstellung ist genau dann minimal, wenn die folgenden Koeffizientenbedingungen erfüllt sind.
   a) Die Koeffizienten ${}a_{i}$, die sich auf ${}1,5,10,50,100$ beziehen, sind ${}\leq 1$.
   b) Die Koeffizienten ${}a_{i}$, die sich auf ${}2,20,200$ beziehen, sind ${}\leq 2$.
   c) Falls der Koeffizient, der sich auf ${}2$ (bzw. ${}20$ bzw. ${}200$) bezieht, gleich ${}2$ ist, so ist der vorhergehende Koeffizient (der sich also auf ${}1$ bzw. ${}10$ bzw. ${}100$ bezieht) gleich ${}0$.
3. Die eindeutige Darstellung findet man, indem man sukzessive absteigend ${}a_{9},\ldots ,a_{1}$ bestimmt, wobei man folgendermaßen vorgeht

   $a_{9}{\text{ ist die maximale natürliche Zahl mit }}a_{9}\cdot 500\leq w,$

   definiere

   ${}w_{8}:=w-a_{9}\cdot 500\,.$

   $a_{8}{\text{ ist die maximale natürliche Zahl mit }}a_{8}\cdot 200\leq w_{8},$

   definiere

   ${}w_{7}:=w_{8}-a_{8}\cdot 200\,,$

   etc.

Zum Beweis, Alternativen Beweis erstellen