Wer kennt sie nicht, die alte Legende von dem klugen Mann, der als Belohnung für irgendwas von seinem Herrscher "nur" ein Schachbrett voller Reiskörner wollte.
1 Korn aufs erste Feld (= 2^0)
2 Körner aufs zweite Feld (=2^1)
4 Körner aufs dritte Feld (=2^2)
usw.
Insgesamt bekommt er dafür dann (2^64)-1 Reiskörner (die genaue mathematische Herleitung spar ich mir).
Jaa, warum ist das eigentlich so? Jeder Informatiker ruft sofort "anschaulich klar", denn der Summe ueber 2
k mit k=0..63 entsprechen im Binaersystem gerade 64 Einsen. Danach kommt eine Eins mit 64 Nullen, und die hat den Wert 2
64.
Leider wissen die Informatiker noch lange nicht, was sie tun! Woher weisz jedes Kind, dasz 1.000.000-1=999.999 ist? Leider in der Regel kaum aus mathematischer Durchdringung der Sache!! ;-)
Die Behauptung ist an sich leicht nachzupruefen: Induktion auf Autopilot nach dem Exponenten. Derselbe Beweis gilt dann auch fuer Zahlensysteme zu beliebiger Basis, womit wir auch bei 999.999+1=10
6 waeren.
Aber wen befriedigt diese hingeworfene Erkenntnis? Es ist ja nicht so, als haetten die Mathematiker im Hinterzimmer ihr rotes Telefon zum lieben Gott und muessten sich nur die zu beweisenden Erkenntnisse durchgeben lassen... ;-)
Die sich aufdraengende Frage ist: Warum funktioniert das Ziffernsystem eigentlich so, wie wir es kennen? Sprich, warum ist die anschauliche Begruending, die ich oben den Informatikern zugeschrieben habe, nicht ein stichhaltiger Beweis?! Wenn wir wirklich wissen, dasz die Stellen die Wertigkeiten 2
k haben und der Nachfolger einer Folge von Einsen eine Eins mit ebensovielen Nullen ist, ist sie das sogar. Okay. Ersteres ist Definitionssache aber letzteres folgt dann mit gerade dem Beweis von oben. :-/ Auszerdem, wer sagt denn eben, dasz wir die Definition so machen sollen wie beschrieben? Warum ergibt die ueberhaupt Sinn? Warum erwischen wir mit dieser Darstellung ueberhaupt alle natuerlichen Zahlen (und warum keine doppelt)? Naja, wir ordnen unsere Zahlendarstellungen der Reihe nach (0, 10, 11, 100, 101, 110, ...) und behaupten, dasz diese Folge dem Wert nach genau den natuerlichen Zahlen 0,1,2,3,... entspricht. Das ist ein bisschen Tueddelei, aber der entscheidende Schritt ist eben wieder der Uebergang von 1111... auf 10000..., also der Satz von oben. Zusammengefasst: Der ganze Scheisz ist keine Begruendung fuer unsere Formel, sondern eine
Folge aus ihr! Hrmpf.
Irgendwie muss man doch auf diesen Ziffernquatsch kommen, ohne sich diese Definition inkl. Formel aus dem Hintern zu ziehen (okay, und ohne sich in die Pampa zu setzen und auszuprobieren :-P)!
Die Antwort lautet, wenig verwunderlicher Weise,
Division mit Rest. Das ist eine der natuerlichsten Operationen. Multiplikation kann jeder, kommt gleich nach Addition. Und Division ist deren Umkehrung. Und mit Rest, naja, so gut es eben geht. ;-) Man stelle sich etwa die Szene aus dem Chinesischen Restsatz (okay, leicht anderes Thema :-P) vor: Eine Armee von soundsovielen Millionen. Aber wieviele denn? Naja, einfach in Zehnerreihen aufstellen lassen! Alle bis auf einen aus jeder Reihe duerfen gehen, und dann nochmal! Je oefter das geht, desto mehr hat man. :-D Und wenn mans genau wissen will, muss man sich bei jedem Durchlauf merken, wieviele uebrig geblieben sind. In Formeln (q
0=Staerke der Armee, p=Basis des Ziffernsystems -- z.B. 10 oder 2):
q
0 = pq
1 + r
0 q
1 = pq
2 + r
1 q
2 = pq
3 + r
2 ...
So ergibt sich eine Folge (r
i), die irgendwann konstant 0 wird, naemlich wenn q
n=0 erreicht ist. Das passiert frueher oder spaeter, weil die q
i streng monoton fallen (den Beweis spare ich mir :-P). Es sind leicht zu nachzuvollziehen:
- Die Kenntnis aller ri bestimmt den Ausgangswert q0 vollstaendig, d.h. wir brauchen uns nichts weiter zu merken fuer unsere Zahlendarstellung. Wir taufen die ri hiermit Ziffern. ;-)
- Der Wert von q0 aendert sich, wenn wir eine der Ziffern aendern, d.h. die Zuordnung einer Zahl zu ihrer Ziffernfolge ist eindeutig, es gibt keine "doppelten".
- Jede natuerliche Zahl laeszt sich so zerlegen, d.h. unser System ist vollstaendig.
Man stellt jetzt durch rekursives Einsetzen fest, dasz die Zahl q
0 tatsaechlich die Darstellung als Summe ueber r
ip
i mit i=0..n hat! Und der Beweis ist genau so eine Autopilot-Induktion wie die eingangs benannte. Und das bekannte Verhalten bei Uebertrag (Ziffern kippen auf 0) ergibt sich auch direkt:
qi+1 = { p(qi+1+1) + 0 , falls ri=p-1pqi + (ri+1) sonst
D.h. wenn wir nur "volle Ziffern", also z.B. Einsen bei p=2, haben, kippen sie bei Inkrement um 1 alle um, und oben kommt eine neue hinzu. Sprich: Die Informatiker hatten doch recht. :-)
