Satz über die minimale Bargeld-Darstellung
Es gelten die folgenden Aussagen.
- Jede natürliche Zahl besitzt eine eindeutige Summendarstellung
-
(mit )
mit der Eigenschaft, dass die Gesamtanzahl der Summanden
(also )
unter allen Darstellungen minimal ist.
- Eine solche Darstellung ist genau dann minimal, wenn die folgenden Koeffizientenbedingungen erfüllt sind.
a) Die Koeffizienten , die sich auf beziehen, sind .
b) Die Koeffizienten , die sich auf beziehen, sind .
c) Falls der Koeffizient, der sich auf
(bzw. bzw. )
bezieht, gleich ist, so ist der vorhergehende Koeffizient
(der sich also auf bzw. bzw. bezieht)
gleich .
- Die eindeutige Darstellung findet man, indem man sukzessive absteigend bestimmt, wobei man folgendermaßen
vorgeht
-
definiere
-
-
definiere
-
etc.