Qbi's Weblog

In einem Rätsel fragte ich vor kurzem nach der Lösung zu folgendem Problem:

Wenn man das Ganze nun 29mal macht, also 2²⁹, erhält man eine neunstellige Zahl. Diese neun Zahlen sind voneinander verschieden. Da wir im normalen Leben mit 10 Zahlen (0, ..., 9) rechnen, muss hier also eine fehlen. Die Frage ist, welche Zahl ist das?

Nach den Kommentaren zu urteilen, haben viele ihre Lieblingsprogrammiersprache angeworfen, gerechnet und hatten das Ergebnis. Der Witz an dem Rätsel ist aber, die Lösung ohne solche Hilfsmittel und ohne explizites Errechnen zu ermitteln. Wie sieht nun ein möglicher Weg aus?

Überlegt euch zunächst mal ein paar Eigenschaften einer Zahl, die alle Ziffern von 0 bis 9 (im folgenden mal Oberzahl genannt) genau einmal enthält. Ist diese durch 2, 3, 4 usw. teilbar?

Was relativ schnell klar sein sollte, ist, dass die Zahl sowohl durch 3 als auch durch 9 teilbar ist. Die Teilbarkeitseigenschaft wird in beiden Fällen über die Quersumme ermittelt. Das Ergebnis von 0+1+2+3+4+5+6+7+8+9 wusste bereits der kleine Herr Gauß (und brachte damit seinen Lehrer zur Verzweiflung) und ist 45 (9*(9+1)/2). Da diese Zahl durch 3 und 9 teilbar ist, muss auch die ursprüngliche durch 3 und 9 teilbar sein. Wenden wir uns insbesondere der Teilbarkeit durch 9 zu.

Stellt euch vor, wir ziehen von der Oberzahl (also der, die alle Zahlen von 0 bis 9 einmal enthält) 1 ab und schauen, ob das Ergebnis durch 9 teilbar ist. Dies ist natürlich nicht mehr der Fall. Dividieren durch 9 ergibt irgendetwas mit Rest 8 (oder auch mit Rest -1). Auch die Quersumme ist nun 44, also eine Zahl, die den Rest 8 (oder auch -1) ergibt, wenn man sie durch 9 teilt. Andererseits könnte man von der Oberzahl einfach eine Zahl weglassen und schauen, was Division durch 9 ergibt. Wenn ihr also die 1 aus der Zahl entfernt, ist die Quersumme wieder 44, also eine Zahl mit Rest 8 (modulo 9). Das heißt, mit diesem Wissen müssen wir uns nun anschauen, welchen Rest die Zahl 2²⁹ bei der Division mit 9 hat.

Im einfachsten Fall kann man sich dazu die ersten Glieder der Folge ausrechnen und schauen, ob es Regelmäßigkeiten gibt:
2⁰=1?=1 (mod 9)
2¹=2?2 (mod 9)
2²=4?4 (mod 9)
2³=8?8 (mod 9)
2⁴=16?7 (mod 9)
2⁵=32?5 (mod 9)
2⁶=64?1 (mod 9)
2⁷=128?2 (mod 9)
2⁸=256?4 (mod 9)
Wer die Notation nicht kennt: n (mod 9) bedeutet, geteilt durch 9 mit Rest n.

Es ist hier also ein Zyklus 1, 2, 4, 8, 7, 5 zu erkennen. Wenn man den Zyklus bis 29 betrachtet, erhält man das Ergebnis 2²⁹=5 (mod 9).

Der eher mathematische Weg wäre, den Satz von Euler geeignet auszunutzen. Da muss man die obigen Schritte nicht mühselig per Hand rechnen, sondern bekommt das Ergebnis gleich präsentiert.

Im obigen Beispiel war das Ergbnis Rest 8, da von der Oberzahl 1 abgezogen wurde. Hier erhalten wir als Ergebnis 5. Also fehlt in 2²⁹ die Zahl 4.

Bild von eqqman