wenn man die Nummerierung der Zeilen und Spalten bei 0, statt bei 1 beginnen läßt, gilt:
a_ij=i XOR j 
für das Feld a_ij in der i-ten Zeile und j-ten Spalte.
An der Kreuzung der 6666665-ten Zeile mit der 7654320-ten Spalte steht also der Wert:
11001011011100110101001 XOR 
11101001100101110110000 = 
00100010111001000011001 = 1143321

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)

\
Um mal etwas für die Vielfalt der Lösungen zu tun:

Wir zeigen, dass für a,b\in \N die Zahl (a XOR b) die kleinste natürliche Zahl ist, die nicht in der Menge M(a,b)= {(a XOR c),c<b}\union{(c XOR b),c<a} vorkommt.
Offenbar ist (a XOR b) nicht in M(a,b), denn verknüpfen mit XOR mit einer festen Zahl ist eine Involution.
Es reicht also zu zeigen, dass jedes n<(a XOR b) in M(a,b) enthalten ist. Schreibt man ein solches n binär als n=((x_0 x_1 x_2 ...))_2=\sum(x_i 2^i,i=0,\infty), so unterscheidet es sich von (a XOR b)=((y_0 y_1 y_2 ...))_2 
an irgendwelchen Stellen i_1 < ...< i_k. Da n< (a XOR b) muss dabei x_i_k=0 und y_i_k=1 sein. Demnach ist genau eine der beiden i_k-ten Binärstellen in a oder in b eine 1. ObdA in a. Ändere in a genau die Binärstellen i_1 , ... ,i_k und erhalte a'<a (weil bei der i_k-ten Stelle von 1 zu 0 geändert wird!).
Dann ist (a' XOR b) = n.

Die XOR - Tabelle erfüllt also dieselbe Bildungsvorschrift, wie die gegebene und startet mit derselben Anfangszahl in der Ecke. Also sind sie gleich. 1143321 ist demnach das Ergebnis.

Gruss, Robert

\
Das ist wirklich eine Aufgabe, die zum Mitmachen einlädt und ein sehr schönes Ergebnis hat. Beim MPCT war das die Aufgabe, an der alle ihre Freude hatten.

Selbstverständlich verlief die Suche nach der Lösung nicht so zielgenau, wie Plex' Beweis (also, nicht bei mir). Die Erkenntnis mit XOR kommt, wenn man erkannt hat, daß jedes 2^n\cross\ 2^n-Quadrat in 4 Teile zerfällt (siehe das passende Bild von Plex dazu). Diese 4 Teile kann man (auf der Ebene n) als 0\-Block und 1\-Block ansehen, womit ich meine (was Plex ja auch sagt), daß im 1 Block alle Werte a_ij um 2^n größer sind, als die entsprechenden Werte im 0\-Block. 

Ich führe eine Abkürzung ein Q(n+1) := 2^(n+1)\cross\ 2^(n+1)-Quadrat
Dann liegt das gesuchte a_ij entweder im oberen rechten Viertel \small\(off topic: das hier muß die Aufgabe für Dietmar sein) \normal\ oder links oben oder rechts unten. Liegt es im oberen rechten Viertel, dann kann man den Wert a_ij auch an der Stelle a_(i-2^n, j-2^n) suchen, also im Q(n) weitersuchen. Liegt es aber in einem der 1\-Blöcke, dann ist sein Wert um 2^n größer als der entsprechende Wert im Q(n). Die 2^n muß man sich dann auf einen Summenzähler addieren. 

Daraus habe ich dann eine Rekursion gebaut und als ich das dann durchrechnete, da wurde mir klar, daß genau die 2\-er\-Potenzen auf den Summenzähler addiert werden, bei denen i und j nicht das gleiche Bit haben.

@Eckard: Danke für diese Aufgabe.

Gruß
Matroid