Ich will zeigen, dass folgende Rekursionsformel gilt:
a_((2^n+r_1)(2^m+r_2))=\fdef(a_((r_1)(r_2)), falls m=n;2^n+a_((r_1)(2^m+r_2)) , falls n>m;2^m+a_((2^n+r_1)(r_2)), falls m>n)
für alle n,m>=0 und 0<=r_1<2^n, 0<=r_2<2^m
und, dass in dem ersten 2^u x 2^u Block des Schachbretts jeweils alle Zahlen
von 0 bis 2^u-1 in jeder Zeile und Spalte vorkommen.
Beweis durch Induktion über \ max(n,m):
Für \ max(n,m)=0:
Der erste 2^0 x 2^0 Block sieht so aus:
10
01
a_((2^0+0)(2^0+0))=a_11=0=a_00
Sei nun \ max(n,m)=u und gelte die Behauptung für \ max(n,m)<u
Dann liegt die Zahl a_((2^n+r_1)(2^m+r_2)) in dem ersten 2^(u+1) x 2^(u+1) - Block (siehe Skizze).
Nach Induktionsvoraussetzung kommen in dem ersten 2^u x 2^u Block (A) alle Zahlen von 0 bis 2^u-1 in jeder
Zeile und jeder Spalte vor.
Betrachte nun den 2^u x 2^u - Block rechts daneben.
Da links davon in jeder Zeile jede Zahl von 0 bis 2^u-1 vorkommt, ist die erste zulässige Zahl, die man
in dem rechten Block eintragen darf 2^u, die Reihenfolge der Zahlen ist aber die gleiche wie im A-Block.
Also braucht man nur 2^u zu jedem Eintrag zu addieren -> A+2^u.
Betrachte nun den 2^u x 2^u - Block über dem A-Block.
In jeder Spalte darunter kommt jede Zahl von 0 bis 2^u-1 vor mit
der gleichen Begründung, wie oben, muß dieser also =A+2^u sein.
Nun fehlt noch der 2^u x 2^u Block rechts oben.
Da in den Blöcken daneben die Zahlen 0 bis 2^u-1 noch nicht vorkommen, kann man einfach
den A-Block diagonal nach rechts oben verschieben.
Wenn nun m=n gilt, liegt das Feld a_((2^n+r_1)(2^m+r_2)) im A-Block
rechts oben, also gilt a_((2^n+r_1)(2^m+r_2))=a_((r_1)(r_2))
Wenn n>m oder m<n gilt, liegt das Feld a_((2^n+r_1)(2^m+r_2)) in einem der A+2^u Blöcke
Falls n=u gilt also
a_((2^n+r_1)(2^m+r_2))=2^n+a_((r_1)(2^m+r_2))
(das Feld liegt dann im Block links oben)
und entsprechend
falls m=u
a_((2^n+r_1)(2^m+r_2))=2^m+a_((2^n+r_1)(r_2))
(das Feld liegt dann im Block rechts unten)