Zum Inhalt springen

Eurozahlen/Eindeutige Darstellung/Charakterisierung/Fakt

Aus Wikiversity
Satz über die minimale Bargeld-Darstellung

Es gelten die folgenden Aussagen.

  1. Jede natürliche Zahl w besitzt eine eindeutige Summendarstellung
    w=a1⋅1+a2⋅2+a3⋅5+a4⋅10+a5⋅20+a6⋅50+a7⋅100+a8⋅200+a9⋅500

    (mit a1,…,a9∈ℕ) mit der Eigenschaft, dass die Gesamtanzahl der Summanden (also a1+a2+⋯+a9) unter allen Darstellungen minimal ist.

  2. Eine solche Darstellung ist genau dann minimal, wenn die folgenden Koeffizientenbedingungen erfüllt sind.
    a) Die Koeffizienten ai, die sich auf 1,5,10,50,100 beziehen, sind ≤1.
    b) Die Koeffizienten ai, die sich auf 2,20,200 beziehen, sind ≤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 a9,…,a1 bestimmt, wobei man folgendermaßen vorgeht
    a9 ist die maximale natürliche Zahl mit a9⋅500≤w,

    definiere

    w8:=w−a9⋅500.
    a8 ist die maximale natürliche Zahl mit a8⋅200≤w8,

    definiere

    w7:=w8−a8⋅200,

    etc.