Die Geschichte des kleinsten trimagischen Quadrats
Geschrieben
von Walter Trump im Januar 2003
Am 25.04.2002 machte mich Aale de Winkel, ein Freund aus Holland, auf eine neue Internetseite mit der Adresse www.multimagie.com aufmerksam. Der Franzose Christian Boyer beschreibt auf dieser Seite die historische Entwicklung der multimagischen Quadrate und die Entdeckung der ersten tetra- und penta-magischen Quadrate durch ihn selbst und seinen Freund André Viricel. Ein multimagisches Quadrat ist ein magisches Quadrat, das magisch bleibt, wenn man von allen seinen Zahlen bestimmte Potenzen bildet (hoch 2, hoch 3, ...).
Für die Konstruktion multimagischer Quadrate der Ordnung n ist die Berechnung multimagischer Reihen von Bedeutung; das sind alle möglichen Kombinationen von n verschiedenen natürlichen Zahlen kleiner gleich n², deren Summen der ersten, zweiten, ... Potenzen jeweils einen bestimmten konstanten Wert ergeben. Mit anderen Worten, unter allen Zahlenfolgen sind dies die potenziellen Kandidaten für die Zeilen und Spalten der multimagischen Quadrate.
1 + 19 +
23 + 24 + 36 + 42 + 53 + 62 =
260 = (1 + 2 + ... +
64 ) / 8 |
Zwischen Christian Boyer und mir entstand eine rege E-Mail-Konversation über bimagische Reihen. Mitte Mai hatte er die Idee von bimagischen zu TRImagischen Reihen überzugehen und bat mich seine Anzahl von 121 trimagischen Reihen der Ordnung 8 zu überprüfen. Am 18. Mai bestätigte ich dieses Ergebnis. Dies war der Startschuss für die Suche nach trimagischen Quadraten.
Unter anderem diskutierten wir darüber, ob es ein kleineres trimagisches Quadrat gibt, als das von Benson gefundene, es hat die Ordnung 32 (d.h. 32 Zeilen und 32 Spalten). An dieser Diskussion beteiligten sich, wenn auch weniger intensiv, noch weitere Liebhaber magischer Quadrate aus aller Welt. Einige vermuteten, dass 32 bereits die kleinstmögliche Ordnung wäre (z. B. George Chen aus Taiwan), andere meinten 27 (André Viricel aus Frankreich), keiner zog Ordnungen unter 16 in Erwägung.
Christian Boyer hatte bereits nachgewiesen, dass Ordnungen kleiner 10 nicht in Frage kommen. Ich konnte mit anderen Methoden seine Ergebnisse bestätigen und zusätzlich beweisen, dass es kein trimagisches Quadrat mit der Ordnung kleiner 12 geben kann.
Im Rahmen dieser Überlegungen berechneten wir für kleine Ordnungen n alle trimagischen Reihen. Bis zur Ordnung 10 konnten diese relativ schnell ermittelt werden. Bei der Ordnung 11 kam ich nach Berichtigung eines kleinen Fehlers auf die gleiche Anzahl wie Christian Boyer. Um alle trimagischen Reihen der Ordnung 12 zu finden, waren einige Tage Rechenzeit (auf einem gewöhnlichen PC) notwendig. Ich fand nicht weniger als 2 226 896 trimagische Reihen der Ordnung 12. Bislang wurde dieses Ergebnis von niemandem bestätigt. Alle Reihen bestehen aus 6 geraden und 6 ungeraden Zahlen.
1 5
45 69 73 143 70 72 74 86
90 142 |
Nun stellte sich die Frage, ob man aus den trimagischen Reihen auch tatsächlich ein trimagisches Quadrat der Ordnung 12 bilden kann. Stellen Sie sich das Folgende wie die Suche nach einem goldenen Schatz vor. Wo soll man suchen? Wie soll man suchen? Existiert der goldene Schatz überhaupt?
Würde man mit 'Brute Force' (d. h. mit roher Gewalt) zum Ziel kommen? Man könnte mit dem Computer normale magische Quadrate der Ordnung 12 berechnen und jeweils testen, ob zusätzlich trimagische Eigenschaften vorliegen. Ein solcher Versuch scheitert kläglich an der immens großen Anzahl von magischen Quadraten der Ordnung 12. Nach meinen statistischen Näherungen beträgt die Anzahl dieser Quadrate nämlich mehr als 10188 (eine Zahl mit 189 Stellen - jenseits jeder menschlichen Vorstellungskraft).
Ein anderer Ansatz könnte darin bestehen 12 unabhängige trimagische Reihen zu finden, welche die Zeilen des Quadrats bilden. Anschließend könnte man die Zahlen innerhalb der Zeilen umordnen bis auch die Spalten trimagische Reihen sind. Doch auch dieser Weg ist wenig erfolgversprechend, weil die prognostizierten Rechenzeiten bei einigen Milliarden Jahren liegen.
Das ‚Gebiet’ für die Schatzsuche musste noch enger begrenzt werden. Deshalb wurde die Suche auf so genannte achsensymmetrische Quadrate beschränkt. Bei diesen ist die Summe von zwei symmetrisch gelegenen Zahlen stets gleich n²+1. Zwei Zahlen mit dieser Summe werden komplementär genannt. Für die Zeilen kamen jetzt nur noch symmetrische trimagische Reihen in Frage und für die Spalten solche ohne komplementäre Zahlenpaare. Außerdem braucht nur noch die linke Hälfte des Quadrats (72 Zahlen) berechnet werden, die rechte ergibt sich aus der Symmetrie.
Damit stand das Gebiet der Schatzsuche fest, aber noch nicht die Suchmethode. Wenn man nach Gold sucht, kann man zunächst prüfen ob überhaupt Metall vorhanden ist. Wenn man nach magischen Quadraten sucht, kann man zunächst nach so genannten semi-magischen Quadraten Ausschau halten. Bei diesen Quadraten spielt die Summe der Zahlen in den Diagonalen keine Rolle.
Bei semi-magischen Quadraten bleiben die Eigenschaften erhalten, wenn man die Zeilen bzw. Spalten umordnet. Daher kann man eine beliebige Zahl in das linke obere Feld setzen. Ich wählte die Zahl 23, weil sie am häufigsten innerhalb der trimagischen Reihen vorkommt. Damit ergeben sich nur noch 3 646 Möglichkeiten für die erste Zeile, 107 099 Möglichkeiten für die erste Spalte, 33 004 für jede weitere Zeile und 473 663 für jede weitere Spalte. Das sind immer noch viel zu viele Möglichkeiten für eine Trial-and-Error-Strategie. Wenn man die erste Zeile und die erste Spalte vorgibt, müssen nur noch 55 Zahlen berechnet werden. Mit einem Trick ist es möglich, die potenziellen trimagischen Zeilen und Spalten mit jeweils nur einer einzigen 64-Bit-Zahl auszudrücken. Mit Hilfe der AND-Funktion kann man nun extrem schnell feststellen, ob zwei Reihen gemeinsame Zahlen enthalten. Zunächst wird die erste Spalte um fünf weitere unabhängige Spalten ergänzt. Dabei kommt ein Backtracking-Verfahren zum Einsatz. Das heißt, man versucht alle möglichen Wege zu beschreiten, gelangt man in eine Sackgasse, so kehrt man zur letzten Wegkreuzung zurück. Auch die Zeilen werden mit einem Backtracking-Verfahren gesucht. Dabei muss nicht nur die Unabhängigkeit der Zeilen beachtet werden, sondern es muss zusätzlich jede Zeile mit jeder Spalte jeweils genau eine Zahl gemeinsam haben.
Zur Umsetzung des Algorithmus verwendete ich die Programmiersprache GB32, die in Deutschland von Gfa-Soft entwickelt wurde, im Wesentlichen von Frank Ostrowski. GB32 ist sehr gut zur Lösung mathematischer Probleme geeignet und zu Unrecht relativ unbekannt. Die erste Fassung des Programms wurde im Mai 2002 fertiggestellt. Einige Stunden Rechenzeit führten nur zu einem Teilerfolg, mehrere beinahe trimagische Quadrate, bei denen 4 Spalten nicht den trimagischen Forderungen entsprachen, wurden gefunden. Am 1. Juni wurde ein beinahe magisches Quadrat gefunden, bei dem alle 12 Zeilen und 10 Spalten trimagisch waren.
53 |
67 |
74 |
69 |
1 |
3 |
142 |
144 |
76 |
71 |
78 |
92 |
79 |
72 |
64 |
5 |
35 |
7 |
138 |
110 |
140 |
81 |
73 |
66 |
118 |
11 |
9 |
55 |
85 |
68 |
77 |
60 |
90 |
136 |
134 |
27 |
15 |
17 |
13 |
82 |
62 |
57 |
88 |
83 |
63 |
132 |
128 |
130 |
124 |
108 |
122 |
126 |
43 |
56 |
89 |
102 |
19 |
23 |
37 |
21 |
129 |
46 |
36 |
120 |
104 |
29 |
116 |
41 |
25 |
109 |
99 |
16 |
38 |
24 |
34 |
47 |
114 |
18 |
127 |
31 |
98 |
111 |
121 |
107 |
10 |
133 |
95 |
59 |
96 |
33 |
112 |
49 |
86 |
50 |
12 |
135 |
48 |
131 |
75 |
8 |
40 |
39 |
106 |
105 |
137 |
70 |
14 |
97 |
44 |
113 |
139 |
100 |
30 |
42 |
103 |
115 |
45 |
6 |
32 |
101 |
93 |
94 |
125 |
141 |
117 |
65 |
80 |
28 |
4 |
20 |
51 |
52 |
119 |
54 |
84 |
58 |
143 |
22 |
123 |
2 |
87 |
61 |
91 |
26 |
Christian Boyer schrieb daraufhin: (übersetzt aus dem Englischen)
Lieber Walter,
Ich hoffe du bist der "erste in der Welt",
der ein trimagisches Quadrat der Ordnung 12 entdeckt, oder zumindest ein
semi-trimagisches Quadrat. So weit ich weiß arbeitet sonst niemand inder
Welt an diesem Thema, du hast also gute Chancen den Jackpot zu knacken!
12 trimagische Zeilen und 10 trimagische Spalten (und vielleicht eine Diagonale)
sind schon ein unglaublicher Fortschritt auf diesem Gebiet, das hätte ich
mir vor ein oder zwei Wochen niemals vorstellen können.
Christian.
Außerdem formte Christian Boyer das angesprochene Quadrat so um, dass alle Spalten zumindest bimagisch waren und sich in den Diagonalen die normale magische Summe ergab. Also ein magisches Quadrat, das semi-bimagisch und beinahe trimagisch war.
53 |
69 |
71 |
78 |
1 |
142 |
3 |
144 |
67 |
74 |
76 |
92 |
79 |
5 |
81 |
73 |
35 |
138 |
7 |
110 |
72 |
64 |
140 |
66 |
118 |
55 |
136 |
134 |
85 |
68 |
77 |
60 |
11 |
9 |
90 |
27 |
15 |
82 |
132 |
128 |
62 |
57 |
88 |
83 |
17 |
13 |
63 |
130 |
124 |
126 |
23 |
37 |
43 |
89 |
56 |
102 |
108 |
122 |
19 |
21 |
129 |
120 |
109 |
99 |
104 |
29 |
116 |
41 |
46 |
36 |
25 |
16 |
38 |
47 |
111 |
121 |
114 |
18 |
127 |
31 |
24 |
34 |
98 |
107 |
10 |
59 |
50 |
12 |
96 |
33 |
112 |
49 |
133 |
95 |
86 |
135 |
48 |
8 |
70 |
14 |
40 |
106 |
39 |
105 |
131 |
75 |
137 |
97 |
44 |
100 |
6 |
32 |
30 |
103 |
42 |
115 |
113 |
139 |
45 |
101 |
93 |
141 |
20 |
51 |
117 |
65 |
80 |
28 |
94 |
125 |
4 |
52 |
119 |
58 |
61 |
91 |
143 |
22 |
123 |
2 |
54 |
84 |
87 |
26 |
Trotz dieser anfänglichen Teilerfolge zeigte sich, dass das Programm nicht effektiv genug arbeitete. Mit dieser Version hätte es vermutlich Jahre gedauert, bis wenigstens ein semi-trimagisches Quadrat erzielt worden wäre.
Einige Ideen für Verbesserungen des Programms spukten mir im Kopf herum und konkretisierten sich in der Nacht zu Samstag, den 8. Juni 2002. Ich stand gegen 6 Uhr auf und arbeitete die neuen Ideen in das vorhandene Programm ein. Gegen 9 Uhr wurden bereits die ersten semi-trimagischen Quadrate der Ordnung 12 gefunden.
Das erste ‚Metall’ war gefunden. Es musste jetzt geprüft werden ob ‚Gold’ darunter ist. Mit einem weiteren Computerprogramm wurde durch Umordnung der Zeilen und Spalten versucht, trimagische Diagonalen zu erzeugen. Nach wenigen Stunden, genau beim 88. semi-trimagischen Quadrat konnte eine trimagische Diagonale konstruiert werden und aus Symmetriegründen war die andere Diagonale automatisch trimagisch. Aber ich vermutete, dass ein Fehler vorlag, der Erfolg hatte sich an diesem Tag zu schnell eingestellt. Deshalb überprüfte ich alle geforderten Eigenschaften zusätzlich mit einem Tabellenkalkulationsprogramm. Jede Zahl von 1 bis 144 wurde genau einmal verwendet, alle Summen waren korrekt.
1 |
22 |
33 |
41 |
62 |
66 |
79 |
83 |
104 |
112 |
123 |
144 |
9 |
119 |
45 |
115 |
107 |
93 |
52 |
38 |
30 |
100 |
26 |
136 |
75 |
141 |
35 |
48 |
57 |
14 |
131 |
88 |
97 |
110 |
4 |
70 |
74 |
8 |
106 |
49 |
12 |
43 |
102 |
133 |
96 |
39 |
137 |
71 |
140 |
101 |
124 |
42 |
60 |
37 |
108 |
85 |
103 |
21 |
44 |
5 |
122 |
76 |
142 |
86 |
67 |
126 |
19 |
78 |
59 |
3 |
69 |
23 |
55 |
27 |
95 |
135 |
130 |
89 |
56 |
15 |
10 |
50 |
118 |
90 |
132 |
117 |
68 |
91 |
11 |
99 |
46 |
134 |
54 |
77 |
28 |
13 |
73 |
64 |
2 |
121 |
109 |
32 |
113 |
36 |
24 |
143 |
81 |
72 |
58 |
98 |
84 |
116 |
138 |
16 |
129 |
7 |
29 |
61 |
47 |
87 |
80 |
34 |
105 |
6 |
92 |
127 |
18 |
53 |
139 |
40 |
111 |
65 |
51 |
63 |
31 |
20 |
25 |
128 |
17 |
120 |
125 |
114 |
82 |
94 |
Bildschirm angezeigt. Die Suche nach dem kleinsten trimagischen Quadrat wurde erfolgreich abgeschlossen.
Am nächsten Tag verschickte ich das Zahlenquadrat per E-Mail an alle mir bekannten Freunde der magischen Quadrate und bat sie um Überprüfung des Resultats. Einige Antworten können im Anhang nachgelesen werden, alle bestätigten die Richtigkeit des Ergebnisses.
Ich bedanke mich insbesondere bei Christian Boyer (Frankreich), der durch seine Veröffentlichungen und Ideen die Suche eingeleitet hat. Ohne seine eigenen Beiträge und seine kritische Prüfung meiner Berechnungen wäre die Suche nicht erfolgreich gewesen. Mein Dank gilt auch Aale de Winkel (Holland), der mich im Laufe des Jahres immer wieder ermutigt hat, auf dem Gebiet der magischen Quadrate weiter zu arbeiten. Ähnlichen Rückhalt erfuhr ich auch von Harvey Heinz (Kanada) und George Chen (Taiwan).
Walter Trump, Nürnberg, Januar 2003
Reaktionen, per E-Mail, auf die Entdeckung des kleinsten
trimagischen Quadrats
(Alle Texte waren ursprünglich in Englisch
verfasst und wurden nachträglich übersetzt.)
Christian Boyer (Frankreich, ehemaliger technischer Direktor von Microsoft France, Gründer einer Softwarefirma, Entdecker der ersten tetra- und penta-magischen Quadrate, Webpublisher: www.multimagie.com)
Lieber Walter,
Exzellentes Quadrat! Unglaubliches Ergebnis! Besser
als das berühmte Quadrat von Benson!
Wie gewünscht habe ich die Eigenschaften
überprüft und natürlich ist alles in Ordnung.
Und alle Zahlen von 1 bis
144 sind vorhanden ;-)
Damit wird dir die Ehre zuteil, in meiner Tabelle
der Rekorde eingetragen zu werden.
Gratulation.
Christian Boyer.
Yung C. Chen, alias George Chen (Taiwan, Begründer von Konstruktionsmethoden, Author kombinatorischer Abhandlungen)
Lieber Walter,
Gratulation.
Wo ein Wille ist, da ist ein Weg.
Deine
Errungenschaft ist fabelhaft, sie ist ein Meilenstein auf dem Gebiet der
magischen Quadrate.
Viele Grüße
George
Aale de Winkel (Niederlande, Physiker und Informatiker, publiziert die magic square encyclopedia)
Lieber Walter
Gratulation, ich habe die trimagischen Eigenschaften
verifiziert,...
... dies ist in der Tat ein erstaunliches Ergebnis.
Es
wäre großartig dein trimagisches Quadrat der Ordnung 12 in die "Encyclopedia"-Datenbank
aufzunehmen (aber ich vermute, es wäre klug diese Entdeckung in einer wissenschaftlichen
Zeitschrift zu veröffentlichen)
Grüße
Aale
Harvey Heinz (Kanada, Autor des Buches Magic Square Lexicon, betreut die weltweit umfangreichste Website über magische Quadrate.)
Gratulation Walter, du hast den Jackpot geknackt.
Das besonders
Außergewöhnliche an dieser Leistung ist der Umfang in dem du den bisherigen
Rekord gebrochen hast!
Vorherige Rekordhalter konnten den alten Rekord
jeweils nur halbieren. Dein Ergebnis ist ein Drittel des alten.
Junge,
ich wette du warst begeistert als du das Ergebnis des Quadrats Nummer 88
gesehen hast! Wir alle teilen deine Begeisterung.
Wie Christian kann
ich es kaum erwarten, etwas darüber auf meiner Internetseite zu berichten.
Aber
ich warte auf dein O.K.. Du wirst vermutlich die Veröffentlichung in einem
mathematischen Journal vorziehen. Das ist jedoch auch etwas für die lokalen
Zeitungen und die Nachrichtensender. Magische Quadrate interessieren auch
die Allgemeinheit.
Nochmals viele Glückwünsche, Walter.
Erstmal viele
Grüße
Harvey
Zurück zur Homepage http://www.multimagie.com