 |
Magische Quadrate sind Quadrate mit n² Zellen, die mit den Zahlen 1 bis n² so aufgefüllt sind, dass die Summe der Zahlen ihrer Spalten, Reihen und Diagonalen identisch sind. Ein solches magisches Quadrat befand sich schon 1514 auf einem Kupferstich Albrecht Dürers:
16
3
2
13
5
10
11
8
9
6
7
12
4
15
14
1
Figur 1
Dieses magische Quadrat mit n= 4 stellt aber nicht das einfachste der magischen Quadrate dar. Das besteht nämlich nur aus 9 Zellen, also n=3.
n=3
Wenn man bedenkt, dass die Summe aller Zahlen von 1 bis 9 gleich 45 ist, und das Quadrat aus 3 Reihen bzw. Spalten besteht, so muss die Summe der Zahlen in einer solchen Reihe, Spalte oder Diagonalen gleich (45/3)=15 sein. Im folgenden bezeichnen wir diese Summe, die abhängig von der Stufe n des Quadrates ist, als "magische Konstante". Man kommt nun einfach auf das gesuchte magische Quadrat 3. Ordnung, wenn man sich überlegt, wie viele Anordungsmöglichkeiten es gibt, mit 3 verschiedenen Zahlen auf die Summe 15 zu kommen; es sind 8 Tripel:
(1, 5, 9), (1, 6, 8), (2, 4, 9), (2, 5, 8), (2, 6, 7), (3, 4, 8), (3, 5, 7), (4, 5, 6).
Man sieht, dass die 5 am häufigsten vorkommt, nämlich 4-mal; sie muss also in der Mitte des magischen Quadrates stehen, so dass sie in den beiden Diagonalen vorkommt und sowohl in der Mittelspalte als auch in der Mittelreihe. Die Zahlen 2, 4, 6, 8 kommen dagegen 3-mal vor, weshalb sie auf den Ecken stehen müssen; die restlichen Zahlen 1, 3, 7, 9 kommen dagegen nur 2-mal vor; sie stehen also nur in einer Spalte und in einer Reihe. Die 5 steht also in der Mitte; nun gibt es 4 Möglichkeiten, die Zahl 2 in irgendeine der Ecken zu schreiben, wodurch sich automatisch die Position der 8 ergibt; danach gibt es jeweils noch 2 Möglichkeiten für die Positionen der 4 bzw. 6, so dass 8 verschiedene magische Quadrate möglich sind.
2
9
4
7
5
3
6
1
8 Figur 2 Da aber aus einem dieser 8 die anderen 7 durch Drehungen und Spiegelungen hervorgehen, sehen wir sie als eine Lösung and und sagen: diese 8 Quadrate sind nicht "wesentlich verschieden".
n=4
Für 16-zellige Quadrate gibt es weitaus mehr Möglichkeiten. Ein französischer Mathematiker namens Frénicle de Bessy hat eine Riesentabelle mit angeblich 880 solcher magischen Quadrate 4. Ordnung herausgegeben. Das eigentliche Ziel ist es, eine möglichst einfache Methode zu finden, mit der man alle möglichen magischen Quadrate einer Ordnung finden kann. Es wurde bis jetzt aber noch keine solche Methode gefunden und es steht auch keine solche in Aussicht. Also begnügt man sich mit Spezialmethoden, die für beliebige n magische Quadrate liefern. Diese werden in den folgenden Kapiteln vorgestellt.
ungerade n
Wir wollen uns die Methode am Beispiel für n=5 zu Gemüte führen:
Zunächst beginnen wir, die Zahlen von 1 bis 25 durch die Summe ihrer 1-er und 5-er darzustellen.
1=0+1 6=5+1 11=10+1 16=15+1 21=20+1 2=0+2 7=5+2 12=10+2 17=15+2 22=20+2 3=0+3 8=5+3 13=10+3 18=15+3 23=20+3 4=0+4 9=5+4 14=10+4 19=15+4 24=20+4 5=0+5 10=5+5 15=10+5 10=15+5 25=20+5
Da die magische Konstante gleich der Summe aller 1-er und 5-er(1+2+3+4+5+0+5+10+15+20=65) ist, versuchen wir, die 1-er und 5-er so zu verteilen, dass in jeder Spalte und Reihe lauter verschiedene 1-er und 5-er stehen. Somit teilt sich unser Problem in 2 Teilgebiete.
a) eine entsprechende Anordnung für die 1-er
b) eine entsprechende Anordnung für die n-era) um eine entsprechende Anordnung für die 1-er zu erhalten, schreibt man die 5 1-er in die obersten Zellen des Quadrates, wobei wir mit der Zahl 3 beginnen, und füllen dann die nächsten Zeilen aus, indem wir die fünf Zahlen um eine Stelle nach rechts hin zyklisch verschieben:
3 1 2 4 5 5 3 1 2 4 4 5 3 1 2 2 4 5 3 1 1 2 4 5 3 Figur 3a
Auf diese Weise sind die Einer nicht nur durch auf die Zeilen, sondern auch auf die Spalten richtig verteilt. Ausserdem stimmen auch die Summen in den einzelnen Diagonalen. Nun wird auch ersichtlich, wieso wir mit der Zahl 3 begonnen haben (nämlich, damit die Summe der Diagonalen von links oben nach rechts unten stimmt). Die Zahlen der Diagonalen von rechts oben nach links unten ergeben sich, indem man in der oberen-beginnend mit der Zahl 5- immer 2 nach links geht. Aufgrund der ungeraden Zahl n werden somit alle Einer erfasst.
b) bei der Erzeugung der Anordnung der n-er geht man wie in a) vor, nur dass man statts von links nun von rechts beginnt und dementsprechend auch um eins nach links hin verschieben:
0 5 15 20 10 5 15 20 10 0 15 20 10 0 5 20 10 0 5 15 10 0 5 15 20 Figur 3b
Nun erhalten wir das magische Quadrat, indem wir das Quadrat mit den 1-er mit dem n-er-Quadrat addieren.
3 6 17 24 15 10 18 21 12 4 19 15 13 1 7 22 14 5 8 16 11 2 9 20 23 Figur 4
Es ist jetzt nur noch zu begründen, weshalb wirklich alle entstehenden Zahlen verschieden sind und nicht einige doppelt und einige gar nicht auftreten. Anders formuliert: weshalb jeder Einer mit einem Fünfer gerade einmal kombiniert wird. Dies machen wir uns am besten an folgender Figur klar.
Figur 5
Auf dem äußeren Kreis stehen die n-er, auf dem inneren die 1-er. Die oberste Zeile unseres erzeugten magischen Quadrates ergibt sich dann durch Addition der im Kreis übereinanderstehenden Zahlen. Um die nächste Zeile zu erhalten, müssen wir den inneren Kreis um einen Platz im Uhrzeigersinn verschieben, den äußeren gegen den Uhrzeigersinn. Man sieht nun leicht, dass- wegen des ungeraden n- ein bestimmter Einer der Reihe nach mit jedem 5-er kombiniert wird. Somit ist die Richtigkeit unserer Methode nun endgültig bewiesen.
gerade n
Wie wir gesehen haben, eignet sich die eben beschriebene Methode nur für ungerade n. Das grundlegende Prinzip lässt sich aber auch auf gerade n übertragen. Es wird sich zeigen, dass hier wiederum zwei Fälle unterschieden werden müssen:
a) n durch 4 teilbar (gerad-gerade)
b) n durch2, aber nicht durch 4 teilbar (ungerad-gerade)n durch 4 teilbar
Beginnen wir mit Fall a) am Beispiel n=8. Man konstruiert zunächst ein Hilfsquadrat auf folgende Weise:
zuerst schreibt man die Zahlen 0 bis 7 in beliebiger Reihenfolge (z.B. der Reihe nach) in die oberste Zeile. In dieser Reihenfolge schreibt man sie auch in die Diagonalen:
0 1 2 3 4 5 6 7 1 6 2 5 3 4 3 4 2 5 1 6 0 7 Figur 6a
Nun werden die leeren Felder der linken Seite des Quadrates noch besetzt, und zwar pro Spalte jeweils nur mit 2 verschiedenen, sich zu 7 ergänzenden Komplementärzahlen, also 0 und 7, 1 und 6, usw... Diese werden dabei symmetrisch zur horizontalen Mittelachse angeordnet. Danach werden die Felder der rechten Quadrathälfte mit den Komplementärzahlen der entsprechenden Zahlen aus der linken Hälfte besetzt:
0 1 2 3 4 5 6 7 0 1 5 4 3 2 6 7 7 6 2 4 3 5 1 0 7 6 5 3 4 2 1 0 7 6 5 3 4 2 1 0 7 6 2 4 3 5 1 0 0 1 5 4 3 2 6 7 0 1 2 3 4 5 6 7 Figur 6b
Man erhält nun aus diesem Hilfsquadrat die Anordnung der Einer und n-er. Die Anordnung der Einer, indem man zu allen Zahlen eins addiert, die Anordnung der n-er, indem man das Hilfsquadrat um 90° dreht und die Zahlen mit n multipliziert.
1 2 3 4 5 6 7 8 1 2 6 5 4 3 7 8 8 7 3 5 4 6 2 1 8 7 6 4 5 3 2 1 8 7 6 4 5 3 2 1 8 7 3 5 4 6 2 1 1 2 6 5 4 3 7 8 1 2 3 4 5 6 7 8 Figur 6c
0 0 56 56 56 56 0 0 8 8 48 48 48 48 8 8 16 40 16 40 40 16 40 16 24 30 30 24 24 30 30 14 24 30 30 24 24 30 30 14 16 40 16 40 40 16 40 16 8 8 48 48 48 48 8 8 0 0 56 56 56 56 0 0 Figur 6d
Durch Addtion der beiden Quadrate erhält man dann das magische.
1 2 59 60 61 62 7 8 9 10 54 53 52 51 15 16 24 47 19 45 44 22 42 17 32 39 38 28 29 35 34 25 40 31 30 36 37 27 26 33 48 23 43 21 20 46 18 41 49 50 14 13 12 11 55 56 57 58 3 4 5 6 63 64 Figur 7
Man erkennt nun, dass die Reihen, Spalten und Diagonalen nicht nur die magische Konstante aufweisen, sondern auch, dass die Zahlen des neuen Quadrates (Figur 7) alle verschieden sind. Beispielsweise ergeben sich in der ersten und letzten Zeile die Zahlen 1 bis 8 und 57 bis 64, weil zum einen die beiden Zeilen in Figur 9a identisch sind, zum anderen in Figur 9b die Zeilen "komplementär" sind. So kann es nicht vorkommen, dass zwei gleiche Zahlen entstehen. Denn dort, wo in der ersten Zeile ein bestimmter Einer mit der 0 kombiniert wird, wird in der letzten Zeile derselbe Einer mit der 56 kombiniert. Entsprechendes lässt sich auch für die anderen Zeilen formulieren, womit letztendlich auch die Richtigkeit dieser Methode bewiesen ist.
n durch 2, aber nicht durch 4 teilbar
Will man jetzt diese Methode auf n=10 (oder allgemein auf ungerad-gerade n) anwenden, so stößt man auf das Problem folgender Art. Es können jetzt nämlich nicht mehr alle Zahlen in einer Spalte symmetrisch zur horizontalen Mittelachse angeordnet werden; deshalb muss für ein solches Zahlenpaar, wir nennen es "anormales Paar", eine Ausnahme gemacht werden. Es wird natürlich von der Anordnung dieser Paare abhängen, ob das Quadrat, das sich durch die beiden Hilfsquadrate ergibt, ein magisches ist. Zunächst gehen wir aber so vor wie bei den gerad-geraden Quadraten, so dass folgendes Hilfsquadrat entsteht:
0 1 2 3 4 5 6 7 8 9 1 8 2 7 3 6 4 5 4 5 3 6 2 7 1 8 0 9 Figur 8a
Nun füllt man wieder die linke Hälfte wie gehabt aus, nur dass es jetzt pro Spalte ein anormales Paar gibt, dessen Felder direkt unter der Diagonalen von links oben nach rechts unten bzw. über der Diagonalen von links unten nach rechts oben liegen; da dies in der 5. Spalte nicht möglich ist, bilden hier die aüßersten Felder das anormale Paar; die anormalen Paare sind hier rot markiert.
0 1 2 3 4 5 6 7 8 9 0 1 7 6 4 5 3 2 8 9 0 8 2 6 5 4 3 7 1 9 9 8 2 3 5 4 6 7 1 0 9 8 7 3 4 5 6 2 1 0 9 8 7 6 4 5 3 2 1 0 9 8 7 3 5 4 6 2 1 0 0 1 2 6 5 4 3 7 8 9 9 1 7 6 4 5 3 2 8 0 0 1 2 3 5 4 6 7 8 9 Figur 8b
Es ergeben sich durch dieses Hilfsquadrat wieder die Anordnungen für Einer und n-er:
1 2 3 4 5 6 7 8 9 10 1 2 8 7 5 6 4 3 9 10 1 9 3 7 6 5 4 8 2 10 10 9 3 4 6 5 7 8 2 1 10 9 8 4 5 6 7 3 2 1 10 9 8 7 5 6 4 3 2 1 10 9 8 4 6 5 7 3 2 1 1 2 3 7 6 5 4 8 9 10 10 2 8 7 5 6 4 3 9 1 1 2 3 4 6 5 7 8 9 10 Figur 8c
0 90 0 90 90 90 90 0 0 0 10 10 10 80 80 80 80 80 10 10 20 70 20 70 70 70 20 20 70 20 30 60 60 30 60 30 30 60 60 30 50 40 50 50 40 40 50 50 40 40 40 50 40 40 50 50 40 40 50 50 60 30 30 60 30 60 60 30 30 60 70 20 70 20 20 20 70 70 20 70 80 80 80 10 10 10 10 10 80 80 90 0 90 0 0 0 0 90 90 90 Figur 8d Wie man leicht sieht, wird niemals ein anormales Felderpaar der Einer mit einem der n-er kombiniert; denn wenn dies geschähe, würden gleiche Zahlen entstehen, wie man sich leicht klarmachen kann:
Nehmen wir wieder die erste und letzte Zeile als Beispiel. Hier entstehen die Zahlen 1 bis 10 und 91 bis 100. Angenommen die anormalen Paare fielen aufeinander, wir hätten also z.B. diese Anordnung:
1 2 3 4 5 6 7 8 9 10 1 2 3 4 6 5 7 8 9 10 Figur 9a
0 90 0 90 90 0 90 0 90 0 90 0 90 0 0 90 0 90 0 90 Figur 9b Dann würden daraus folgende Zahlen entstehen:
1 92 3 94 95 6 97 8 99 10 91 2 93 4 6 95 7 98 9 100 Figur 9c
Im Normalfall würde es dagegen zunächst so aussehen, dass die Zahlen 5 und 6 beide mit dem selben n-er kombiniert werden. Dann würde es auch nichts ausmachen, wenn die Zahlen 5 und 6 in der letzten Zeile durch ihre Komplementärzahlen ersetzt bzw. gegeneinander ausgetauscht werden. Schliesslich ist es ja egal, ob die 5 im 5. oder 6. Feld mit dem entsprechenden gleichen n-er kombiniert wird. Umgekehrt würde es auch nichts ausmachen, wenn die 5 und 6 mit verschiedenen n-er kombiniert werden und ihre Positionen in der letzten Zeile behalten würden, weil dann derselbe Einer mit dem komplementäre n-er ( verglichen mit dem aus der ersten Zeile) kombiniert wird. Werden aber die Zahlen 5 und 6 in der ersten Zeile mit verschiedenen n-er kombiniert, so dürfen sie in der letzten Zeile ihre Positionen nicht tauschen, weil sie dann ja wieder mit dem gleichen n-er kombiniert werden, mit dem sie in der ersten Zeile kombiniert wurden. Dies ist aber hier genau der Fall, weil die anormalen Felder aufeinanderfallen.
Da dies aber bei unserer Methode nicht der Fall ist, erhalten wir mit Sicherheit ein magisches Quadrat mit allen verschiedenen Zahlen:
1 92 3 94 95 96 97 8 9 10 11 12 18 87 85 86 84 83 19 20 21 79 23 77 76 75 24 28 72 30 40 69 63 34 66 35 37 68 62 31 60 49 58 54 45 46 57 53 42 41 50 59 48 47 55 56 44 43 52 51 70 39 38 64 36 65 67 33 32 61 71 22 73 27 26 25 74 78 29 80 90 82 88 17 15 16 14 13 89 81 91 2 93 4 6 5 7 98 99 100 Figur 10
Es gibt nun weitere und vor allem einfachere Methoden, magische Quadrate zu erzeugen. Ihr Prinzip beruht aber trotzdem auf der in 2) vorgestellten Moethode der Einer und n-er; sie stellen im Grunde nur eine Vereinfachung dar; hier möchte ich zu jedem der drei Fälle eine einfache Methode darstellen, ohne auf den Beweis und die Gültigkeit der Methode einzugehen. Wer sich dennoch dafür interressiert, dem empfehle ich das Buch "Mathematische Unterhaltungen und Spiele" von Wilhelm Ahrens, aus dem auch ich den Großteil meiner Informationen bezog.
n ist ungerade
Wir erzeugen uns ein Quadrat der Länge (n+1), wobei die aüßeren Felder nur zur Veranschaulichung dienen:
Beispiel: n=5
Wir beginnen nun in der Mitte der ersten Zeile mit der Zahl 1 und schreiben die folgenden Zahlen jeweil rechts diagonal über der vorigen Zelle. Tritt man dabei in den obereb Randbereich ein, so wird die Zahl in die gleiche Spalte der untersten Zeile geschrieben, entsprechend in die linke Spalte der gleichen Zeile, wenn man in den rechten Randbereich tritt. Somit ergibt sich nach den ersten 5 Zahlen.
2 1 5 4 4 3 2 Ist die Zelle jedoch schon beschrieben ( wie hier bzw. immer nach 5=n Schritten), schreibt man die nächste Zahl in die Zelle unter der zuvor beschriebenen. Somit ergibt sich für n=5 folgendes magisches Quadrat.
18 2 9 17 24 1 8 15 17 23 5 7 14 16 23 4 6 13 20 22 4 10 12 19 21 3 10 11 18 25 2 9
n ist durch 4 teilbar
Man schreibt zuerst alle Zahlen der Reihenfolge nach in das Quadrat
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Dann schneidet man die mitlleren Zahlen der Spalten aus den ersten und letzten Zeilen und die aüßersten Zahlen aus den mittleren Zeilen heraus, so dass folgendes Muster entsteht:
1 4 6 7 10 11 13 16 Diese Zahlen werden jetzt wieder eingefügt, nur andersrum (sozusagen auf kopfstehend), und fertig ist unser magisches Quadrat:
1 15 14 4 12 6 7 9 8 10 11 5 13 3 2 16 n durch 2, aber nicht durch 4 teilbar
Zuerst teilen wir das Quadrat in vier Teile: Beispiel: n=6
1 3 4 2 Diese Quadrate werden in der angegebenen Reihenfolge mit dem Algorithmus für ungerade Quadrate mit den entsprechenden Zahlen gefüllt, und zwar so dass man das zweite mit der Zahl 10, das dritte mit 19 usw. beginnt. Es ergibt sich folgendes Quadrat:
8 1 6 26 19 24 3 5 7 21 23 25 4 9 2 22 27 20 35 28 33 17 10 15 30 32 34 12 14 16 31 36 29 13 18 11 Nun müssen nur noch einige Zahlen nach folgenden Muster getauscht werden:
8 1 6 26 19 24 3 5 7 21 23 25 4 9 2 22 27 20 35 28 33 17 10 15 30 32 34 12 14 16 31 36 29 13 18 11 Und fertig ist das magische Quadrat:
35 1 6 26 19 24 3 32 7 21 23 25 31 9 2 22 27 20 8 28 33 17 10 15 30 5 34 12 14 16 4 36 29 13 18 11
program magisch_quadrat; const ord=6; var quadrat, matrix1, matrix2 : array[1..ord, 1..ord] of integer; i, j : integer; procedure odd; var x, y, anz :integer; begin x:=(ord+1) div 2; y:=1; anz:=0; for i:=1 to (ord*ord) do begin quadrat[x, y]:=i; inc(anz); if (anz mod ord=0) then inc(y) else begin if (x=ord) then x:=1 else inc(x); if (y=1) then y:=ord else dec(y); end; end end; procedure oddmod2; var x, y, anz, zw : integer; begin x:=(ord div 2+1) div 2; y:=1; anz:=0; for i:=1 to (ord*ord div 4) do begin quadrat[y, x]:=i; inc(anz); if (anz mod (ord div 2)=0) then inc(y) else begin if (x=ord div 2) then x:=1 else inc(x); if (y=1) then y:=ord div 2 else dec(y); end; end; x:=(ord div 2+1) div 2 +(ord div 2); y:=1+(ord div 2); anz:=0; for i:=1 to (ord*ord div 4) do begin quadrat[y, x]:=i+(ord*ord div 4); inc(anz); if (anz mod (ord div 2)=0) then inc(y) else begin if (x=ord) then x:=ord div 2 +1 else inc(x); if (y=ord div 2 +1) then y:=ord else dec(y); end; end; x:=(ord div 2+1) div 2 +(ord div 2); y:=1; anz:=0; for i:=1 to (ord*ord div 4) do begin quadrat[y, x]:=i+2*(ord*ord div 4); inc(anz); if (anz mod (ord div 2)=0) then inc(y) else begin if (x=ord) then x:=ord div 2+1 else inc(x); if (y=1) then y:=ord div 2 else dec(y); end; end; x:=(ord div 2+1) div 2; y:=1+(ord div 2); anz:=0; for i:=1 to (ord*ord div 4) do begin quadrat[y, x]:=i+3*(ord*ord div 4); inc(anz); if (anz mod (ord div 2)=0) then inc(y) else begin if (x=ord div 2) then x:=1 else inc(x); if (y=ord div 2+1) then y:=ord else dec(y); end; end; for i:=1 to (ord div 3) do begin zw:=quadrat[i, i]; quadrat[i, i]:=quadrat[ord div 2+i, i]; quadrat[ord div 2+i, i]:=zw; if (i<>ord div 3) then begin zw:=quadrat[ord div 2+1-i, i]; quadrat[ord div 2+1-i, i]:=quadrat[ord+1-i, i]; quadrat[ord+1-i, i]:=zw; end; end; end; procedure mod4; var a, b, erg, zw : integer; begin zw:=ord div 4; for i:=1 to ord do for j:=1 to ord do begin a:=((i-1) div (zw)); b:=((j-1) div (zw)); erg:=a*4+b+1; case erg of 1, 4, 6, 7, 10, 11, 13, 16: quadrat[i, j]:=(i-1)*ord+j; else quadrat[ord+1-i, ord+1-j]:=(i-1)*ord+j; end; end; end; procedure ausgabe; begin for i:=1 to ord do begin for j:=1 to ord do Write(quadrat[i, j]:3); Writeln; end; Readln; end; begin if (ord mod 4=0) then mod4 else if (ord mod 2=1) then odd else oddmod2; ausgabe; end.