Mathematische
Unterhaltungen
Manche
magischen Quadrate haben eine innere Struktur,
die
es erlaubt, aus einem einzelnen magischen Quadrat viele andere
zu
machen.
Von
Christoph Pöppe
Kann man
ein Brett aus 5 x 5 quadratischen Feldern rnit fünf Farben so kolorieren, daß jede
pro Zeile und Spalte nur einmal vorkommt?
Das ist
nicht schwer Man verteilt die fünf Farben beliebig auf die Felder der ersten
Zeile. Diese Anordnung kopien man um ein Feld nach rechts versetzt in die
nächste Zeile; das nach rechts überstehende Feld fügt man links in die
Leerstelle dieser Zeile ein. In derselben Weise entsteht aus der zweiten Zeile
die dritte, und so weiter. Diese Methode funktioniert für Quadrate jeder Größe.
Eine
Anordnung, welche die genannte Bedingung erfüllt, heißt lateinisches Quadrat.
Der Name rührt daher, daß der Baseler Mathematiker Leonhard Euler (1707 bis
1783), der seit seinem 20. Lebensjahr in Sankt Petersburg, dann in Berlin und
schließlich wieder in Sankt Petersburg wirkte und außer vielen anderen Dingen
auch solche Quadrate systematisch untersuchte, lateinische Buchstaben anstelle
der Farben verwendete.
Die Anzahl
der Felder je Zeile beziehungsweise Spalte heißt Ordnung des Quadrats. Ein
Quadrat der Ordnung n hat also n² Felder.
Wird
zusätzlich gefordert, daß auch in den Diagonalen jede Farbe nur einmal
veitreten ist, muß man das geschilderte Verfahren etwas abwandeln, denn es
färbt alle Felder der Hauptdiagonale (von links oben nach rechts unten) gleich.
Für Quadrate ungerader Ordnung versetze man die Felder beim Übergang von einer
Zeile zur nächsten nicht um eins nach nechts sondern um zwei; für gerade
Ordnung ist die Situation komplizierter.
Interessanter
wird das Problem. wenn jedes Feld zwei Kennzeichen trägt, etwa eine Innen- und
eine Außenfarbe oder -wie bei Euler - einen lateinischen und einen griechischen
Buchstaben. Dabei ist nicht nur verboten. ein Kennzeichen mehr als einmal in
eine Zeile oder Spalte zu setzen; zusätzlich ist vorgesschrieben, daß jede
Kombination von Kennzeichen nur etnmal vorkommen darf. Ein griechisch-lateinisches
Quadrat entspicht also einem Paar lateinischer Quadrate, die in gewissem Sinne
so verschieden voneinander sind wie nur möglich: Beispielsweise müssen die
Randflächen der Felder, deren Innenfarbe Rot ist, sämtliche vorkommenden Farben
tragen; sonst wäre eine Kombination doppelt vertreten. Ein solches Paar von
Quadraten (eines besteht aus den Innenfarben, das andere aus den Außenfarben)
heißt orthogonal - eine etwas weit hergeholte Metapher aus der Geometrie, wo
zwei gleich lange Vektoren voneinander maximal verschieden sind, wenn sie
aufeinander senkrecht (orthogonal) stehen.
Ein Paar
orthogonaler lateinischer Quadrate der Ordnung 5 ist noch mit mäßiger Mühe zu
finden: Man nehme das Quadrat mit der Versetzung 2 und sein Spiegclbild, wobei die
Hauptdiagonale Spiegelachse ist (Bild 2 links) Für andere Ordnungen kann die
entsprechendeAufgabe extrem schwierig werden. So glaubte Euler, es gebe keine
griechisch-lateinischen Quadrate der Oidnungen 6, 10, 14 und so weiter
(ungerade Vielfache von 2), weil er trotz intensiver Suche keine gefunden
hatte. Bezüglich der Ordnung 6 hatte er recht; für die anderen Fälle hat es
immerhin fast 200 Jahre gedauert, bis 1959 E. T, Parker von der Computerfirma
Univac sowie R. C. Bose und S. S. Shrikande von der Universität von North
Carolina (genannt "Euler's spoilers", weil sie damit das ansonsten
strahlende Bild ihres genialen Vorgängers ein wenig befleckt hatten) ein
Gegenbeispiel fanden. Das Magnetlegespiel
,,Gewonnen,
Herr Euler", das Spektrum der Wissenschaft vertreibt, ersatzweise das
entsprechende Diskettenprograrnrn, gibt Ihnen Gelegenheit, ein
griechisch-lateinisches Quadrat der Ordnung 10 selbst zu suchen
Magische
Quadrate
Wenn man aber
erst ein orthogonales Paar ateinischer Quadrate bat, in dem außerdem jede
Diagonale bei wenigstens einem Partner die Verschiedeuheitsbedingung erfüllt,
ist daraus mit leichter Mühe ein magisches Quadrat zu machen
(Bild 2):
Man ersetze die Kennzeichen (Farben beziehungsweise Buchstaben) durch die
Ziffern von 0 bis n - 1 und schreibe in jedes Feld die beiden zugehörigen
Ziffern nebeneinander Die entstehenden zweistelligen Zahlen sind im
Zahlensystem zur Basis n zu verstehen:
In einem 5
x 5-Quadrat bezeichnet 32 die Zahl 3 x 5 + 2, also 17 in der üblichen
Dezimalschreibweise.
Warum ist
das so konstruierte Quadrat magisch? Warum ist die Summe der Zahlen in jeder
Zeile, Spalte und Diagonale die gleiche? Nun, in den Feldern jeder Zeile kommen
in der rechten (Eincr-)Stelle die Ziffern von 0 bis n - 1
jeweils
genau einmal vor, desgleichen in der linken Stelle; also ist (für n = 5)
die Zeilensumme jedesmal (0+1+2+3+4) + 5 x (0+1 + 2 + 3 + 4) = 60) Für die Spalten- und Diagonalensummen gilt
Entsprechendes. Außerdem - zweite Bedingung für magische Quadrate - ist jede
Ziffernkombination und damit jede Zahl zwischen 0 und n² - 1 genau einmal vcrtreten.
Üblicherweise
schreibt man in ein magisches Quadrat der Ordnung n nicht die Zahlen von
0 bis n² - I, sondern von l bis n². Aber ob man zum Wert jedes
Feldes 1 addiert oder nicht, ist für die Eigenschaft ,,magisch"
unwesentlich; und für das Folgende ist es geschickter. bei 0 anzufangen Die magische Konstante (der gemeinsame Wert aller
Zeilen-, Spalten- nnd Diagonalensummen) eines Quadrates der Ordnung n
ist dementsprechend nicht, wie üblich, n(n2 + 1)/2, sondein n(n2
- 1)/2.
Magische
Quadrate haben eine uralte Geschichte. Aus der Zeit des chinesischen Kaisers
Lu-Shu (um 2200 vor Christus) ist ein magisches Quadrat dritter Ordnung
überliefert. Die europäische Tradition hat jahrhundertelang von einem
Manuskript eines Gelehrten namens Manuel Moschopoulus gezehrt, der Anfang
des 15. Jahrhunderts in Konstantinopel
lebte In diesem Manuskript sind bereits Konstruktionsregeln für magische
Quadrate jeder Ordnung aufgeführt. Cornelius Agrippa von Nettesheim (1486 bis
1535) konstruierte magische Quadrate der Ordnungen 3 bis 9, anscheinend nach
den Methoden des Moschopoulos, setzte sie mit den Planeten (im damaligen
Verständnis) Saturn, Jupiten Mars, Sonne, Venus, Merkur und Mond - in dieser
Reihenfolge - in Beziehung und leitete daraus im Wortsinne magische
Eigenschaften der Planeten und der Quadrate her. Berühmt geworden ist das
magische Quadrat vierter Ordnung aus dem Bild ,,Melencolia' von Albrecht Dürer
(1471 bis 1528); es ist so arrangiert, daß das Entstehungsjahr 1514 in der
Mitte der untersten Zeile erscheint.
Das
Konstruktionsverfahren über die griechisch-lateinischen Quadrate
ist nicht unbedingt das einfachste. Es liefert jedoch ein instruktives
Beispiel für eine bisher kaum beachtete Eigenschaft mancher magischen Quadrate:
ihre Zerlegbarkeit
Ich nenne
ein magisches Quadrat edel, wenn es nach Art eines griechisch-lateinischen
Quadrats zusammengesetzt ist, genauer: wenn es in eine Summe zweier (oder
mehrerer) trivial-magischer Quadrate zerlegbar ist. Dabei soll ein Quadrat
trivial-magisch heißen, wenn es gleiche Zeilen-, Spalten- und Diagonalsummen
hat; es muß aber nicht aus lauter verschiedenen Zahlen bestehen, noch nicht einmal
lateinisch sein. Zum Beispiel ist auch ein Quadrat, das in jedem Feld dieselbe
Zahl trägt, trivial-magisch. Ein lateinisches Quadrat ist nicht immer
trivial-magisch, sondern nur dann, wenn auch entlang. seiner Diagonalen keine
zwei Felder gleich sind.
Für die
Konstruktion eines edlen Quadrats muß man, wie gesagt, nicht unbedingt
griechisch-lateinische zu Hilfe nehmen.
So produziert die einfachste Konstruktionsregel für magische Quadrate ungerader
Ordnung stets edle Quadrate (Kasten auf dieser Seite).
Das Austauschverfahren
Zerlegungen
anderer magischer Quadrate ergeben Komponenten, die nicht lateinisch sind,
dafür aber andere, um so interessantere Eigenschaften haben. Eine
Konstruktionsregel für magische Quadrate, deren Ordnung ein Vielfaches von 4
ist, liefeert Beispiele. Das Dürer-Quadrat sowie das Jupiter- und das
Merkur-Quadrat des Agrippa von Nettesheim sind - bis auf Drehungen,
Spiegelungen und das Addieren der obligatorischen Eins - nach diesem Muster
gebaut.
Wesentlicher
Bestandteil des Verfahrens ist ein (gedachter) Stempel, der die acht
Diagonalenfelder eines 4 x 4-Quadrats einfärbt und die restlichen acht
unverändert läßt (Bild 3). Man schreibt zunächst in ein Qnadrat der Seitenlänge
n -wobei n ein beliebiges Vielfaches von 4 ist - die Zahlen von 0
bis n2 - 1 zeilenweise der Reihe nach ein und bestempelt es dann
lückenlos und überlappungsfrei (Bild 3 links). Jede durch den Stempel gefärbte
Zahl vertauscht man nun mit der ebenfalls gefärbten, die ihr in bezug auf den
Mittelpunkt des Quadrats genau gegenüberliegt (Bild 3 rechts). Beide Zahlen
ergänzen sich stets zu n²-1; man nennt solche Paare komplementär.
Ohne
Zweifel enthält das Endprodukt dieser Prozedur nach wie vor alle Zahlen von 0
bis n²-1; es hat ja nur die Hälfte von ihnen die Plätze getauscht. Es
bleibt auch symmetrisch in dem Sinne, daß Paare komplementärer Zahlen einander
bezüglich des Mittelpunktes genau ge genüberstehen.
Aber wie
kommt es, daß alle Zeilen-, Spalten- und Diagonalsummen den richtigen Wert
haben? Man kann nachrechnen, daß das bei dcn Diagonalen schon vorher der Fall
war; und das Verfahren stellt beide Diagonalen lediglich auf den Kopf, denn
alle Diagonalenfelder werden vom Stempel getroffen. Dagegen sind in der
ursprünglichen Anordnung die Summen der oberen Zeilen zu klein und die der
unteren zu groß; Entsprechendes. wenn auch weniger kraß, gilt für die Summen
der Spalten links beziehungsweise rechts von der Mitte. Die Vertauschungsaktion
gleicht diese Abweichungen gerade aus.
Wie das
genau funktioniert, sieht man am besten an Quadraten, deren Ordnung eine Potenz
von 2 ist: 4, 8, 16, 32 und so
Weiter. In
diesem Falle ist nämlich auch n² eine Zweierpotenz, und es liegt nahe,
zur
Zahldarstellung die Basis 2 zu verwenden. Das läuft auf die cornputerübliche
Binärschreibweise hinaus, deren einzige Ziffern 0 und 1 sind. Ein magisches
Quadrat der Ordnung 16 enthält dic Zahlen von 0 bis 16² - 1 = 255; das sind
gerade alle achtstelligen Binärzahlen (führende Nullen mitgeschrieben). Und ebenso, wie man das eingangs
beschriebene 5 x 5-Quadrat, zur Basis 5 geschrieben, in zwei trivial-magische
Quadrate zerlegen kann, deren jedes einer Stelle in der Zahldarstellung
zugeordnet ist, so zerfällt das 16 x 16-Quadrat in acht trivial-magische
Quadrate, deren jedes zu einer Binärstelle gehört (Bild 4): Es ist edel zur
Basis 2.
Alle diese
Komponenten-Quadrate enthalten nur Nullen und Einsen; weil aber die Eins
je nach Komponente eine, zwei oder mehr Stellen links vom (gedachten)
Binär-Komma steht, hat sie den Wert 1, 2, 4, 8, 16, 32, 64 oder 128. Die
Komponenten-Quadrate zeigen ein auffälliges, regelmäßiges. aber nicht ganz
symmetrisches Muster; daran ist zu erkennen, daß das ursprüngliche magische
Quadrat eine globale Ordnug aufweist. Die Symmetrie ist aber gerade nicht so
umfassend, daß ein und dieselbe Kombination schwarzer und weißer Felder an mehr
als einer Position aufträte. Denn
dann hätten
diese beiden Felder den gleichen Zahlenwert. was nicht sein darf.
Wie kommt
diese Ordnung zustande? Es ist sehr einfach, die zu einer Binärzahl komplementäre
Zahl zu finden. Für n =24 = 16
beispielsweise ist n² = 28 256, und n² - 1 = 255 hat die Binärdarstellung 11111111.
Zwei achtstellige Binärzahlen sind genau dann komplementär bezüglich 28 - 1, wenn die
eine da eine Null hat, wo in der anderen eine Eins steht, und umgekehrt. Die
Wirkung des Stempels - die Bildung der Komplementärzahl - besteht also darin,
daß jede Null in der Binärdastellung durch eine Eins ersetzt wird und
umgekehrt. Insbesondere wirkt der Stempel auf jede Binärstelle - und damit auf
jedes Komponenten-Quadrat - unabhängig von den anderen: Wo er trifft,
vertauscht er Schwarz und Weiß. Somit genügt es, sich zu vergewissern, daß der
Stempel aus jeder Zerlegungs-Komponente des Quadrats, mit dem alles begann (mit
den Zahlen in der natürlichen Reihenfolge). ein trivial-magisches Quadrat macht
(Kasten links).
Umformungen
Hat man
erst einmal ein magisches Quadrat, so kann man daraus durch einfache
Umformungen viele neue machen. Eine zwei oder drei Vierteldrehungen sowie
Spiegelungen an einer Diagonalen oder Mittelsenkrechten lassen die magischen
Eigenschaften unverändert. Das gleiche gilt für kompliziertere Operationen wie
die gleichzeitige Vertauschung zweier komplementärer Spalten und der beiden
zugehörigen Zeilen oder eine weitere, bei der ganze Viertel eines Quadrats in
die diagonal gegenüberliegende Ecke geschoben werden (Bild 5).
Das
Sortiment der Umformungsmöglielkeiten wird durch Zerlegungen erheblich
erweitert, weil die Komponenten einer Zerlegung bis zu einem gewissen Grade voneinander
unabhängig sind. Wenn die Komponenten lateinische Quadrate sind, die auch in
den Diagonalen keine zwei gleichen Elemente enthalten, darf man in jeder
Komponente die Numerierung beliebig ändern. Jede Ziffer darf durch eine andere,
nur dürfen nicht zwei verschiedene Ziffern durch dieselbe ersetzt werden: eine
Permutation. Im zusanrnengcsetzten Quadrat tauschen dadurch zwar gewisse Zahlen
ihre Plätze, aber es stehen dieselben Zahlen im Quadrat wie zuvor, und die
Summenkriterien sind immer noch erfüllt, weil das für die Komponenten gilt.
Wenn, wie beim Standardverfahren für Quadrate ungernader Ordnung. eine
Diagonale n-mal die Zahl (n - 1 )/2 enthält, muß man diese Zahl
unverändert lassen, darf aber die übrigen unbekümmert permutieren.
Bei den
0-1-Komponenten-Quadraten der Binärdarstellung ist die einzig mögliche
Permutation die Vertauschung von Schwarz und Weiß. Immerhin ergibt das für die
acht Komponenten des 16 x 16-Quadrats 28 = 256 Kombinationen. Insbesondere
kann man durch geeignete Wahl der Vertauschungen erzwingen, daß eine
vorgewählte Zahl in die linke obere Ecke (oder in irgendein anderes
vorbestimmtes Feld) gerät.
Der
Kölner Künstler Paul Heimbach hat dieses Prinzip für Quadrate der Ordnung 8
entdeckt, für seine ästhetischen Ziele genutzt und damit den Anstoß zu diesem
Artikel gegeben. Er interpretiert die sechs Komponenten des 8x8-Quadrats als
Masken oder Schablonen, Platten, die anstelle der schwarzen Felder quadratische
Löcher enthalten. Eine Maske nach der anderen legt er auf ein Blatt Papier und
überstreicht sie mit (nicht-deckender) Farbe - jede Maske mit einer anderen.
Heimbach verwendet die Grundfarben Rot, Blau und Gelb in jeweils zwei
verschiedenen Intensitäten, (So ist das Prinzip; die Ausführung kann völlig
anders sein.) Am Ende ergibt sich ein magisches Farbquadrat: Jede Mischung von
null bis zu sechs Maskenfarben ist auf genau einem Feld realisiert. Zusätzlich
ist das Gesamtbild auch noch ausgewogen in dem Sinne, daß jede Maskenfarbe in
jeder Zeile und jeder Spalte in genau der Hälfte der Felder enthalten ist (Bild
1).
Damit
sind die Urnformungsmöglichkeiten noch längst nicht erschöpft. Die Zuordnung
der Masken (und ihrer Farben) zu den Binärstellen ist nämlich keineswegs
zwingend. Was geschieht, wenn man beispielsweise die zweite und die vierte
Maske vertauscht?
An den
Stellen, wo beide Masken schwarz oder beide weiß sind, ändert sieh gar nichts.
Eine Zahl, bei der eine Maske weiß, die andere schwarz ist. tauscht ihren Platz
mit derjenigen, die in diesen beiden Masken die umgekehrte Kombination, in
allen anderen aber denselben Wert hat. Also sind nach wie vor dieselben Zahlen
im Quadrat vertreten, und die Summenkriterien sind ohnehin erfüllt. Für das
Merkur-Quadrat (Ordnung 8) vermehren sich die Variationsmöglichkeiten durch die
Vertauschbarkeit der Masken um den Faktor 6! = 720. Eine von Heimbach erstellte
Compact Disc spielt das ganze Sortiment der so erhältlichen Varianten ab.
Aus einem
einzigen edlen Quadrat der Ordnung 16 ergibt sich durch Umkehrung von Schwarz
und Weiß sowie durch Vertauschung
von Masken ein reichhaltiges Sortiment von insgesamt 256x8! =10321920
Varianten.
Verallgemeinerungen
Bis jetzt.
habe ich gezeigt, wie man edle Quadrate konstruiert, deren Ordnung ungerade
oder eine Zweierpotenz ist. Was ist mit den übrigen Ordnungen?
Man kann
magische Quadrate in einem gewissen Sinne miteinander rnultiplizieren, und das
Produkt zweier edler Quadrate ist wieder edel, wenn man die richtige Zerlegung
wählt. Wie multipliziert man ein Quadrat der Ordnung p mit einem der Ordnung
q (es kommt auf die Reihenfolge der Faktoren an)? Man bläht jedes Feld
des p x p-Qualrats zu einem Block der Größe q x q auf. In alle
Felder eines Blocks schreibt man dieselbe Zahl, und zwar q² mal den
ursprünglichen Wert des Feldes. Dann addiert. man zu jedem Block - Feld für
Feld - das qxq-Quadrat. Das so konstruierte Quadrat hat die Ordnung pq
und ist magisch, denn es enthält jede Zahl von 0 bis (pq)² - 1 genau
einmal und erfüllt die Summenkriterien.
Um
nachzuweisen, daß es auch edel ist, muß man es zerlegen. Dafür gibt es ein
Verfahren, das auf magische Quadrate aller Art (auch unedle) anwendbar ist:
die
Division mit Rest.
Man zerlege
bei einem Quadrat der Ordnung n die Zahl n² irgendwie in
Faktoren, bei ungeradem n zum Beispiel in nxn, bei einer Zweierpotenz
in 2 x2 x ... x 2. Es muß nicht die Prinfaktorzerlegung sein, und die
Reihenfolge der Faktoren ist - zunächst - beliebig. Man dividiere nun das
magische Quadrat Feld für Feld durch den ersten Faktor, schreibe die Quotienten
in ein weiteres Quadrat und die Reste in ein drittes.
Das Quotienten-Quadrat dividiere man in derselben Weise durch den zweiten Faktor; das
ergibt wieder ein Quotienten- und ein Restequadrat, und so weiter, bis die
Faktoren erschöpft sind. Die mit den jeweils korrekten Faktoren multiplizierten
Restequadrate ergeben eine Zerlegung des ursprünglichen Quadrats. Allerdings
sind im allgemeinen die Restequadrate nicht trivial-magisch.
Dieses
Divisionsverfahren läuft auf eine Darstellung der Zahlen des Quadrats bezüglich
einer gemischten Basis hinaus (Spektrum der Wissenschaft, Dczember .1995. Seite
10); die oben besprochenen Zerlegungen zu den reinen Basen 5 und 2 sind
Spezialfälle. Auch in einer Zerlegung zu einer gemischten Basis darf man die
Reihenfolge der Kornponenten vetauschen, was zugleich ihren Stellenwert ändert;
ein edles Quadrat verwandelt sich dadurch in ein anderes, gleichfalls edles.
Warum? Man
zerlege das oben definierte Produktquadrat aus edlen Quadraten der Ordnungen p
und q bezüglich der Faktoren q, q, p, p (in dieser Reihenfolge).
Die ersten beiden Divisionen spalten den Anteil ab, der aus der Addition des q
x q-Quadrats zu jedem Block stammt; also bestehen die zugehörigen
Restequadrate aus der (p x p)-fachen Wiederholung der
Komponentenquadrate des q x q-Quadrats. Die waren nach Voraussetzung
trivial-magisch; also gilt das auch für ihre Wiederholung. Was nach den beiden
ersten Divisionen übrigbleibt, ist das aufgeblähte p x p-Quadrat. Dessen
Zerlegung produziert aufgeblähte Varianten der Komponenten des
p x p-Quadrats.
die offensichtlich ebenfalls trivial-magisch sind. Wenn die ursprünglichen
Quadrate nicht nur edel bezüglich der Zerlegungen p, p beziehungsweise q
, q sind, sondern - wie die Zweierpotenz-Quadrate - noch feinere
Zerlegungen zulassen, bleiben diese Feinheiten bei der Multiplikation erhalten.
Mit dem
Multiplikationsverfahren erreicht man eine Fülle von Ordnungen, jedoch nicht
die ungeraden Vielfachen von 2; denn ein magisches Quadrat der Ordnung 2 gibt
es nicht. Es gibt ein Verfahren, aus einem magischen Quadrat eines doppelter
Ordnung zu machen; leider enthält es - in seiner Ausgestaltung für ungerade
Ordnung - eine Asymmetrie, die eine edle Zerlegung zu vereiteln scheint.
Imrnerhin gibt es ein magisches Quadrat der Ordnung 6, das edel bezüglich der
Zerlegung 6, 6 ist (nicht aber bezüglich 2,2,3,3 - in irgendeiner Reihenfolge).
Allerdings sind seine Komponenten nicht einmal annähernd lateinisch, so daß die
Permutationsmöglichkeiten recht beschränkt sind.
Hier bleibt
noch viel zu tun