Auf Twitter habe ich in meiner Serie #mathepuzzle folgende Aufgabe gestellt:

Auf wieviele verschiedene Arten kann man den Betrag von 1 € aus Centmünzen mit den Werten 1, 2, 5, 10, 20 und 50 zusammensetzen?

Wie kann man das berechnen?

Wir können das Problem umformulieren:
Auf wieviele Arten können wir die Zahl 100 als Summe der Zahlen 1, 2, 5, 10, 20 und 50 darstellen (jede dieser Zahlen darf in der Summe kein mal, einmal oder mehrmals vorkommen).

Mathematiker und Informatiker betten oft so ein Problem in eine Familie verwandter Probleme ein und versuchen, Zusammenhänge zwischen diesen Problemen zu sehen.

Wir machen das auch.

Wir untersuchen, auf wieviele Arten man die Summen, 1, 2, 3, …. 100 bilden kann, und das schrittweise zunächst nur mit 1ern, dann mit 1ern und 2ern, dann mit 1, 2, und 5 usw.
Wir schreiben dazu alle Ergebnisse in einer Tabelle auf.

Der Fall mit lauter 1ern ist einfach. Jeder Summe kann auf genau eine Weise gebildet werden, lauter 1er. Wir haben also die erste Tabelle der Spalte gefüllt, und zwar mit lauter 1ern.

Hat man 1 und 2 zur Verfügung, dann kann die Summe 1 auch nur auf 1 Art (1 1er) gebildet werden, die Summe 2 aber schon auf 2 Arten, (2 1er oder 1 2er). Summe 3 geht ebenfalls auf 2 Arten (1x1 und 1x2 oder 3x1).

Bei der Summe 4 überlegen wir so: Wir können die Summe aus lauter 1ern oder mit mindestens 1 2er bilden. Im zweiten Fall bleibt, wenn wir einen 2er wegnehmen, eine Restsumme von 2, von der wir schon wissen auf wieviele Arten wir sie bilden können. In unserer Tabelle finden wir diese Zahl 2 Zeilen über der Zelle, die wir gerade füllen wollen.

Dieses Prinzip funktioniert immer: Die möglichen Summenkombinationen für die Zahl \(s\), die in Zeile \(s\) und der Spalte mit dem Spaltenkopf 2 unserer Tabelle steht, erhalten wir, indem wir den Wert aus der Zelle links daneben (auf wieviele Arten können wir die Summe \(s\) nur aus 1ern bilden) und den Wert aus der Zelle in derselben Spalte 2 Zeilen darüber (auf wieviele Arten können wir die Summe \(s-2\) aus den Zahlen 1 und 2 bilden) addieren. Dieses Rezept funktioniert für die gesamte Spalte für 2.

Jetzt kommt die Zahl 5 dazu. Wir geben eine weitere Spalte zu unserer Tabelle dazu. Bis Zeile 4 stehen da dieselben Werte wir in der Spalte links daneben (wenn die Summe kleiner als 5 ist, dann können wir die Zahl 5 ja nicht zur Summenbildung verwenden.)

Die Summe 5 können wir entweder ohne Zahl 5 bilden, die entsprechenden Kombinationsmöglichkeiten stehen in der Spalte links daneben, oder es gibt die Lösung mit genau 1x5. Da funktioniert der Trick mit wir nehmen 1x5 weg und schauen, wie oft wir die Restsumme bilden können, noch nicht, weil wir keine Zeile für die Restsumme 0 haben. Wenn wir aber eine Zeile für die Summe 0 einführen und dort für alle möglichen Münz-Sets 1 hinschreiben, dann funktioniert die Methode mit 1 Münze wegnehmen und abzählen, auf wieviele Arten die Restsumme gebildet werden kann, wieder. Die Summe 0 kann auf 1 Art gebilden werden, indem man keine Münze nimmt. (Aus ähnlichen Gründen haben die Mathematiker auch die leere Menge erfunden, nämlich damit, wenn man aus einer Menge alle Elemente wegnimmt, das, was übrig bleibt, immer noch eine Menge ist).

Dieses Verfahren funktioniert auch, wenn wir die Zahlen 10, 20, und 50 zu den erlaubten Summanden hinzufügen.

Bevor wir jetzt das allgemeine Rezept aufschreiben, behandeln wir noch einen Sonderfall. Die Zusammenstellung der erlaubten Summanden muss den 1er nicht immer enthalten. Dann kann man nur mit dem kleinsten erlaubten Summanden nur Summen bilden, die durch diesen kleinsten Summanden teilbar sind. (Beispiel: Wenn der kleinste Summand 2 ist, dann kann man die Summe 3 nicht nur mit dem kleinsten Summanden bilden, die Summe 4 aber schon.)

Wir können also folgendes Rezept zur Berechnung der Kombinationsmöglichkeiten angeben:
Mache ein Tabelle. In der Kopfspalte stehen die Zahlen von 0 bis 100, in der Kopfzeile die erlaubten Summanden in aufsteigener Reihenfolge.
In der ersten Spalte steht 1, wenn die Summe (aus der Kopfspalte) durch den „Spaltensummanden", also die Zahl in der Kopfzeile, teilbar ist, sonst 0. In der Spalte für die Zeilensumme 0 steht überall 1. In den weiteren Spalten steht im oberen Teil die Zahl unmittelbar links daneben, und zwar bis zu der Zeile, deren Summe \(s\) gerade noch kleiner ist als der Spaltensummand. Wenn der Spaltensummand den Wert \(m\) hat, dann steht ab Zeile \(m\) die Summe aus der Tabellenzelle links daneben und der Tabellenzelle aus \(m\) Zeilen darüber (aus derselben Spalte).

Diese Tabelle gibts als Excel-Tabelle zum download.

In dieser Tabelle kann man sehen, dass es 4562 Möglichkeiten gibt, die Summe von 1€ aus Centmünzen zusammenzusetzen.

Nachbemerkung:
Dieses Problem illustriert zwei mathematische Gebiete: Zahlentheorie und Kombinatorik.
Derartige Probleme sind in der Regel nur mit Computerunterstützung lösbar.
Ich denke, dass das ein guter Grund ist, Computer auch im Mathematikunterricht zu verwenden.

Hier noch Code für das Problem in verschiedenen Programmiersprachen

Maxima

How_many_ways(total,coins):=
if total = 0 then 1
else if length(coins)=1 then (if mod(total,last(coins))=0 then 1 else 0)
else (How_many_ways(total,firstn(coins,length(coins)-1)) +
     if(total>=last(coins)) then How_many_ways(total-last(coins),coins) else 0);

How_many_ways(100,[1,2,5,10,20,50])
4562

Mathematica

HowManyWays[0, coins_] := 1
HowManyWays[sum_, coins_] := 
 1 /; (Length[coins] == 1) && (Divisible[sum, First[coins]])
HowManyWays[sum_, coins_] := 
 0 /; (Length[coins] == 1) && (! Divisible[sum, First[coins]])
HowManyWays[sum_, coins_] := HowManyWays[sum, Drop[coins, -1]] /; 
  (sum < Last[coins])
HowManyWays[sum_, coins_] := 
 HowManyWays[sum, Drop[coins, -1]] + 
  HowManyWays[sum - Last[coins], coins] 
  
HowManyWays[100, {1, 2, 5, 10, 20, 50}]
4562

Man kann auch rohe Gewalt verwenden und alle Kombinationen, die irgenwie möglich scheinen, einfach durchprobieren und dann zählen, wieviele davon tatsächlich die gewünschte Summe ergeben:

Listify[el_] := If[ListQ[el], el, List[el]]
CartProd[l1_, l2_] := 
 Outer[Join[Listify[#1], Listify[#2]] &, l1, l2, 1] // Flatten[#, 1] &
 
 HowManyWaysBrute[sum_, coins_] := 
 Map[Floor[sum/#] &, coins] // Map[Range[0, #] &, #] & //
    Fold[CartProd, #] & // Map[Function[x, x.coins], #] & // 
    Select[Function[x, x == sum]] // Length
   
HowManyWaysBrute[100, {1, 2, 5, 10, 20, 50}]
4562

In diesem Algorithmus steckt allerdigs ziemlich wenig Verständnis über die Struktur des Problems, deswegen dauert die Berechnung mit dieser Methode wesentlich länger.