Kommentar | An dieser Stelle kann ich mir die Frage nicht verkneifen: wie viele Möglichkeiten gibt es, einen Euro in Kleingeld zu wechseln? Die Reihenfolge der Münzen soll dabei keine Rolle spielen, nur: wie viele Münzen von welcher Sorte, und der Gesamtwert soll exakt 1 Euro ergeben.
Antwort: 4562 Möglichkeiten.
Man löst das am besten mit einer Excel-Tabelle. Hunderteins Zeilen, die Zeilennummern entsprechen Cent-Werten: Zeile 1 = 0 Cent, Zeile 2 = 1 Cent, usw.
Erste Spalte: wie viele Möglichkeiten gibt es, n Cent (n <= 100) nur durch 1- und 2-Cent-Münzen darzustellen?<br/>1 Möglichkeit für 0 und 1 Cent, 2 Möglichkeiten für 2 und 3 Cent, 3 Möglichkeiten für 4 und 5 Cent, usw. Bei jedem geraden Cent-Wert steigt die Anzahl der Möglichkeiten um 1, bei einem ungeraden bleibt sie gleich.
Zweite Spalte: wie viele Möglichkeiten gibt es, n Cent (n <= 100) nur durch 1-, 2- und 5-Cent-Münzen darzustellen?<br/>Für n<5 ist der Wert gleich der ersten Spalte, denn für so kleine Beträge kann noch kein Fünferl dabei sein.<br/>Für 5<=n<10 ist es (erste Spalte bei n)+(erste Spalte bei n-5), ersteres deckt die Möglichkeiten ohne Fünferl ab, letzteres die Möglichkeiten mit genau einem Fünferl.<br/>Für 10<=n<15 ist es (erste Spalte bei n)+(erste Spalte bei n-5)+(erste Spalte bei n-10), denn für diese Beträge können 0, 1 oder 2 Fünferl dabei sein.<br/>usw.
Dritte Spalte: wie viele Möglichkeiten gibt es, n Cent (n <= 100) nur durch 1-, 2-, 5- und 10-Cent-Münzen darzustellen?<br/>n<10: (zweite Spalte bei n), denn bei einem Betrag unterhalb von 10 Cent kann kein Zehnerl dabei sein.<br/>10<=n<20: (zweite Spalte bei n)+(zweite Spalte bei n-10), ersteres deckt die Möglichkeiten ohne Zehnerl ab, letzteres die Möglichkeiten mit 1 Zehnerl.<br/>20<=n<30: (zweite Spalte bei n)+(zweite Spalte bei n-10)+(zweite Spalte bei n-20), denn hier können 0, 1 oder 2 Zehnerl dabei sein.<br/>usw.
Vierte Spalte: wie viele Möglichkeiten gibt es, n Cent (n <= 100) nur durch 1-, 2-, 5-, 10- und 20-Cent-Münzen darzustellen?<br/>n<20: (dritte Spalte bei n)<br/>20<=n<40: (dritte Spalte bei n)+(dritte Spalte bei n-20)<br/>40<=n<60: (dritte Spalte bei n) + dritte Spalte bei n-20) + (dritte Spalte bei n-40)<br/>usw.
Fünfte und letzte Spalte: wie viele Möglichkeiten gibt es, n Cent (n <= 100) durch 1-, 2-, 5-, 10-, 20- und 50-Cent-Münzen darzustellen?<br/>n<50: (vierte Spalte bei n)<br/>50<=n<100: (vierte Spalte bei n)+(vierte Spalte bei n-50)<br/>n=100: (vierte Spalte bei 100)+(vierte Spalte bei 50)+(vierte Spalte bei 0)=4562 |
---|