Das n-Damen-Problem auf dem Zylinderbrett

Bernd Eickenscheidt, Soester Str. 52, 4400 Münster

Das n-Damen-Problem auf dem Zylinderbrett

Auf dem Schachbrett so viele Damen wie möglich aufzustellen derart, daß sie sich gegenseitig nicht decken, ist ein uraltes, doch immer wieder reizvolles Problem. Für das quadratische Normalbrett ist inzwischen bewiesen, daß man außer bei n=2 und n=3 auf dem n x n-Brett immer genau n Damen unterbringen kann.

Weniger bekannt hingegen sind die Verhältnisse auf dem Zylinder- bzw. Doppelzylinderbrett. Seit dem diesbezüglichen Artikel von Bernd Schwarzkopf (FEENSCHACH Mai-Juni 1970, Blatt 811) hat mir dieses Problem keine Ruhe mehr gelassen, bis ich endlich die letzte Lücke geschlossen hatte in meinem Beweis für die Vermutung, die seinerzeit schon Bernd Schwarzkopf hatte:

"Wenn n weder durch 2 noch durch 3 teilbar ist, dann kann man auf dem n x n-Zylinder- oder Doppelzylinderbrett n ungedeckte Damen unterbringen, UND SONST NICHT."

Zunächst ist klar, daß es bei quadratischen Brettern gleichgültig ist, ob es sich um Zylinder oder um Doppel-zyl inder handelt, denn ein Feld, das man z.B. erreicht, indem man diagonal nach rechts oben geht und beim Erreichen des rechten "Randes" hintenherum links wieder hereinkommt, das kann man genausogut andersherum erreichen (da bei uns ja nie etwas dazwischen steht) und braucht dabei nur den UNTEREN "Rand" zu überschreiten. Aus diesem Grunde sei im folgenden stets "Zylinder oder Doppelzylinder" gemeint, wenn der Kürze halber nur "Zylinder" gesagt wird.

Wir wollen die Linien und Reihen des n x n-Brettes jeweils von 0 bis n-1 numerieren (nicht von l bis n), weil sich so die Beweisführung einfacher darstellen läßt.

Die Diagonalen, die so herum schräg sind wie der mittlere Strich in dem Buchstaben Z, nennen wir Z-Diagonalen und die anderen entsprechend N-Diagonalen. Auf dem n x n-Zylinderbrett gibt es von jeder Sorte Diagonalen gerade wieder n Stück, somit muß bei einer Lösung des n-Damen-Problems genauso wie in jeder Reihe und in jeder Linie auch in jeder Z- und in jeder N-Diagonale genau eine Dame stehen. Was wir jetzt brauchen, ist eine vernünftige Numerierung der Diagonalen. Dazu machen wir uns klar, daß alle Felder, deren Linien-Nummer X und Reihen-Nummer Y dieselbe Summe S=X+Y ergeben, zur gleichen N-Diagonale gehören, und entsprechend alle Felder (X,Y) mit der gleichen Differenz D = X-Y zur gleichen Z-Diagonale. Beim Zylinderbrett müssen wir diese Summe bzw. Differenz allerdings "modulo n" nehmen, wenn dieser Zusammenhang auch umgekehrt gelten soll. Hit "A mod n" sei diejenige Zahl zwischen 0 und n-1 bezeichnet, die sich von A nur um ein Vielfaches von n unterscheidet. (Also ist z.B. 2 mod 10 » 2 , 32 mod 10 = 2 , -18 mod 10 • 2 .) Dann gilt:

Zwei Felder (X1,Y1) und (X2,Y2) gehören genau dann zu der gleichen N-Diagonale, wenn (X1+Y1) mod n = (X2+Y2) mod n ist, und zur gleichen Z-Diagonale, wenn (X1-Y1) mod n = (X2-Y2) mod n ist.

Damit bietet sich folgende Numerierung der Diagonalen an: Alle Felder (X,Y) mit (X + Y) mod n = S bilden die N-Diagonale Nummer S, und alle Felder (X,Y) mit (X-Y) mod n = D bilden die Z-Diagonale Nummer D.

Stehen nun n Damen auf den Feldern (X1,Y1), (X2,Y2) (Xn,Yn), dann

beherrschen sie die Linien Xl,...,Xn, die Reihen Y1,...,Yn, die

N-Diagonalen S1,...,Sn und die Z-Diagonalen Dl,...,Dn, wobei für alle i
die Nummern Si und Di gegeben sind durch:

( 1 ) Si = (Xi+Yi) mod n Di=(Xi-Yi) mod n

Mit diesen Bezeichnungen kann man das n-Damen-Problem auf dem Zylinderbrett folgendermaßen formulieren:

Finde zwei Anordnungen X1,...,Xn und Y1,...,Yn der n verschiedenen Zahlen 0,...,n-1 derart, daß die damit durch die obigen Formeln gegebenen Sl,...,Sn und D1,...,Dn ebenfalls zwei Anordnungen der n verschiedenen Zahlen 0,...,n-1 sind!

Da das Rechnen "modulo n" vielleicht nicht allen Lesern so geläufig ist, soll hier kurz dargestellt werden, welche schönen Eigenschaften diese Operation hat.

Erinnern Sie sich noch an die "Neunerprobe" aus der Schulzeit? Wenn etwa eine Multiplikation A x B zu überprüfen ist, dann bildet man zum einen von A und B die Neunerreste A' = A mod 9 , B' = B mod 9 , multipliziert die und nimmt davon ggf. wfeder den Neunerrest C' = (A' x B') mod 9 , zum anderen nimmt man von dem zu überprüfenden Produkt C • A x B den Neunerrest C'' = C mod 9 und erhält, wenn man richtig gerechnet hat, beide Male dasselbe, C' « C'' . (Daß man die "Neunerreste" effektiv in Form von Quersummen bestimmt, ist eine andere Geschichte.) Das ganze funktioniert ebenso für die Addition und Subtraktion und ist ferner nicht an die Zahl 9 gebunden, d.h. es ist ganz allgemein

( (A mod n) + (B mod n) ) mod n = (A + B) mod n ,

( 2 ) ( (A mod n) - (B mod n) ) mod n = (A - B) mod n ,

( (A mod n) x (B mod n) ) mod n = (A x B) mod n .

Diese Beziehungen werden wir im folgenden ohne weitere Erwähnung ausgiebig benutzen, dadurch wird der Beweis für unsere Behauptung jetzt ganz leicht.

ERSTENS: "Wenn n weder durch 2 noch durch 3 teilbar ist, dann kann man n ungedeckte Damen aufstellen."

Beweis: Für alle i sei Xi = 2i mod n und Yi « i mod n. (Also alle Damen auf den Stationen eines Nachtreiterzuges.) Dann ist nach (1): Si = 3i mod n und Di = i mod n , und weil 2 und 3 zu n teilerfremd sind, sind alle geforderten Bedingungen erfüllt.

ZWEITENS: "Wenn n durch 2 teilbar ist, dann kann man NICHT n ungedeckte Damen aufstellen."

Es gilt sogar noch eine Verschärfung dieser Aussage.

"Mädchen" nenne ich Figuren, die fast dasselbe können wie Damen, aber eben nur fast: Z-Mädchen können orthogonal und in Richtung der Z-Diagonale ziehen, N-Mädchen entsprechend orthogonal und N-diagonal. Wir zeigen:

Wenn n durch 2 teilbar ist, dann kann N-Mädchen aufstellen.

man nicht, einmal n ungedeckte

Beweis: Angenommen man könnte. Dann wäre X1,...,Xn eine Anordnung der n verschiedenen Zahlen 0,...,n-1 und daher die Summe X1+...+Xn dasselbe -- nur in anderer Reihenfolge -- wie 0+...+n-l, das ist gleich n x (n-1)/2 ; bei geradem n ist das modulo n gleich n/2. Aus dem gleichen Grund wäre (Y1+...+Yn) mod n = n/2 und auch

( 3 ) (Sl+...+Sn) mod n = n/2

Andererseits besteht der Zusammenhang (1), woraus man erhält: (S1+...+Sn) mod n • (X1+Y1 + .. ,+Xn+Yn) (mod n

= ( (X1+...+Xn)+(Y1+...+Yn) ) mod n

= (n/2 + n/2) mod n = n mod n = 0,

und das ist ein Widerspruch zu (3), da n/2 und 0 zwei VERSCHIEDENE Zahlen zwischen 0 und n-1 sind.

DRITTENS: "Wenn n durch 3 teilbar ist, dann aufstellen."

kann man NICHT n Damen

Der Fall, daß n durch 6, also durch 3 UND durch 2 teilbar ist, ist unter "zweitens" bereits erledigt. Daher sei jetzt n wohl durch 3, aber nicht durch 2 teilbar, also von der Gestalt n=6m+3.

Dieser Teil des Beweises hat mir über Jahre hinweg Kopfzerbrechen bereitet, weil ich immer wieder unbewußt so etwas ähnliches wie im zweiten Fall versucht habe, was aber gar nicht funktionieren KANN, wie sich gleich zeigen wird. Als "Abfallprodukt" meiner erfolglosen Versuche ist nämlich ein zusätzliches Ergebnis herausgekommen:

Wenn n von der Gestalt n=6m+3 ist, dann kann man n ungedeckte N-Mädchen, aber NICHT n ungedeckte Damen aufstellen.

Beweis des ersten Teiles: Stellen wir die N-Mädchen auf die Felder Xi = Yi « i mod n , also alle auf dieselbe Z-Diagonale, dann ist Si = 2i mod n ; 2 ist teilerfremd zu n, fertig.

Nun zu den Damen, und wiederum indirekter Beweis: angenommen man könnte. Diesmal bilden wir die Summe der QUADRATE X1²+..,+Xn², wieder ist dies -- nur in anderer Reihenfolge -- dasselbe wie 0²+...+(n-l)² , das ist (n-1) x n x (2n-1)/6 , und es ist nicht schwierig auszurechnen, daß das unter den gegebenen Voraussetzungen modulo n gleich 2n/3 ist. (Hinweis: (n-1) x n x (2n-1)/6 = n x (2n²-3n-3)/6 + 4n/6 ; davon ist die Klammer durch 6 teilbar...) Wieder gilt auch entsprechend (Y1²+..,+Yn²) mod n = 2n/3 und Analoges für die Summe der Quadrate der Si bzw. Di. Benutzen wir andererseits die Zusammenhänge (1) und kramen die binomischen Formeln aus der Schublade:

( 4 ) Si² mod n = (Xi²+2XiYi+Yi²) mod n , Di² mod n = (Xi²-2XiYi+Yi²) mod n ,

dann erhalten wir:

(S1²+.,.+Sn²) mod n = (Xl²+...+Xn² + C + Yl² + .. ,+Yn²) mod n

= (2n/3+C+2n/3) mod n = (4n/3+C) mod n * (n/3+C) mod n (wobei unter "C" alle "gemischten Produkte" 2XiYi zusammengefaßt sind), und analog:

(D1²+...+Dn²) mod n = (n/3-C) mod n . mit DEMSELBEN "C". Wie auch immer dieses "C" aussehen mag, es müßte also sowohl (n/3+C) mod n = 2n/3 als auch (n/3-C) mod n = 2n/3 sein; dann erhalten wir durch Addition modulo n der beiden Gleichungen: 2n/3 = 4n/3 mod n = n/3 , also einen Widerspruch! Q.E.D.

Damit ist eine Frage, die zumindest mich seit langem interessiert hat,

eindeutig und endgültig beantwortet.

Es bleibt natürlich noch genug offen: Wenn man NICHT n ungedeckte Damen

aufstellen kann, wieviele denn dann? Und auf wieviele verschiedene

Weisen?

Wer weiß es???