Vorherige Aufgabe   Übersicht 2001   Nächste Aufgabe 

Lösungen der DENKmal-Knobelaufgaben

5. Aufgabe 2001

gestellt am 12. März 2001 in der Knobelecke von
Abenteuer Mathematik - die Welt des Knobelns

Spielgeld

  Aufgabe   Lösung   Antwort 

Aufgabe

Wieviele Möglichkeiten gibt es, 2000 DM mit 2-, 3- und 5-DM-Stücken zu bezahlen (, voraus gesetzt, es gäbe 3-DM-Stücke)?

(eingesandt von Karin Mühlfriedel)

Lösung

Die Anzahl der Möglichkeiten a(n), auf wie viele verschiedene Weisen eine Zahl n (Betrag) als Summe bestimmter anderer Zahlen (Münzen) dargestellt werden kann, lässt ich rekursiv ermitteln.

Es seien M die Menge der verschiedenen erlaubten Münzwerte sowie k und m mögliche Elemente daraus.
Wenn man von einer Summendarstellung für n den Summanden mit dem höchsten Wert m weg lässt, erhält man eine Darstellung für n-m mit höchstem Wert nicht größer als m.
Die Anzahl der Möglichkeiten a(n,m) für m<n, bei denen der höchste Wert nicht größer als m ist, ist also die Summe aller Anzahlen a(n-k,k) mit k ≤ m, wobei im Falle k=n als Summand 1 bzw. 0 zu addieren ist, je nachdem, ob es eine Münze mit dem Wert k gibt oder nicht.

Bei n=2000 und M={2,3,5} erhält man so das Ergebnis a(2000) = a(2000,5) = 67001.
Im folgenden Formular berechnet ein JavaScript-Programm die Anzahlen für alle höchstens 4-stelligen Zahlen nach diesem Algorithmus:


 DM

Für die Werte der Folge a(n) gibt es eine Näherungsformel:
a(n) ≈ n2/60+n/6+1

Antwort

Es gibt 67001 Möglichkeiten, 2000 DM mit 2-, 3- und 5-DM-Stücken zu bezahlen.