Mathematische Knobelei |
19.10.2007
Lösungsvorschlag
Tödlicher Alleingang
Gewinn
Gewinner
Dietmar Viertel
Die Maus wird schon einen langen Atem brauchen, denn so schnell sind die Flöhe nicht gezählt.
Sehen wir uns einmal ein paar Quersummen an. Die Quersumme 1 ergibt sich nur aus der Zahl 1. Die Quersumme 2 ist in der 2 und der 11 enthalten, die Gang mit der Nummer 2 hätte damit zwei Mitglieder. Die Quersumme 3 findet sich in den Zahlen 3, 12, 21 und 111, das sind vier Mitglieder, die Gang mit der Nummer 4 schließlich hat acht Flöhe, denn 4 ist die Quersumme von 4, 13, 31, 22, 112, 121, 211 und 1111.
Das kann man nun in einer großen Tabelle systematisch zählen. Wenn man die Ziffern von 1 bis 9 nebeneinander schreibt und jeweils darunter, wie oft die Ziffer in der Zahl vorkommt, deren Quersumme 23 ergibt, werden es genau 887 Zeilen. Ziemlich viel Arbeit.
Es gibt aber eine elegantere Lösung. Der Schlüssel ist ziemlich lang und lautet:
a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) + a(n-5) + a(n-6) + a(n-7) + a(n-8) + a(n-9)
Das ist eine raffinierte, neunstufige Fibonacci-Folge. Für n=0 bis n=40 liefert die Folge die Zahlen 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16 272, 32 512, 64 960, 129 792, 259 328, 518 145, 1 035 269, 2 068 498, 4 132 920, 8 257 696, 16 499 120, 32 965 728, 65 866 496, 131 603 200, 262 947 072, 525 375 999, 1 049 716 729, 2 097 364 960.
Das Raffinierte ist: Mit der Einschränkung n ≥ 8 liefert diese rekursive Folge die Anzahl ganzer Zahlen die keine Null enthalten und deren Quersumme gleich n-8 ist. Eine zugegebenermaßen schwierige Lösung.
Testen wir die Formel doch mal für Gangstergruppe 4. Die Quersumme ist also 4 = n - 8, das gibt n=12. Und a(12) = a(11) + a(10) + a(9) + a(8). Nun ist a(8) = 1und a(9) = a(8) = 1. Damit ist a(10) = 2, a(11) = 4 und a(12) schließlich 4 + 2 + 1 + 1 = 8. Die Probe stimmt also. Und mit Mathematica oder auch Excel VBA kann man dann leicht ausrechnen: a(23) = 4 132 920
Fertig? Moment noch. Sir John ist ja tot, einer fehlt also, womit das Ergebnis schließlich 4 132 919 lautet. Ob die Maus das überlebt hat?
