Arctic Circle Theorem

In diesem Artikel wollen wir uns mit dem "Arctic Circle"-Theorem beschäftigen. Wir beginnen damit die Überdeckungen von Schachbrettern oder karierten Brettern mit Dominosteinen zu untersuchen. Wir werden das faszinierende Theorem besprechen und schließlich auf mögliche Anwendungen hinweisen.

Schachbretter und Dominosteine

Normales und Brett mit abgeschnittenen Ecken werden mit Dominosteinen belegt

Ein typisches Schachbrett besteht aus einem Brett mit 8 x 8 Feldern. Diese sind abwechselnd Schwarz und Weiß. Bei Schachbrett und Domino geht es darum ein Schachbrett so mit Dominosteinen Auszulegen, dass diesen komplett mit diesen bedeckt ist. Bei einem normalen Brett mit 8 x 8 Feldern, passen auf die 64 Felder genau 32 Dominosteine. Die Frage die man sich jetzt vielleicht stellt ist, ob man, wenn man 2 Felder auf der Diagonale Entfernt, ob man das Brett noch mit den 31 Steinen belegen kann. Aus dem Bauch heraus würde man schnell sagen, dass dies möglich ist. Doch wenn man nun probiert das Feld zu belegen wollen irgendwie immer 2 gleichfarbige Felder, die nicht nebeneinander liegen, übrigbleiben. Der Beweis ist einfach! Denn als Grundüberlegung betrachten wir erst einmal einen Dominostein. Ein Dominostein belegt zwei Felder die nebeneinander liegen. Deshalb überdeckt ein Dominostein genau ein weißes und ein schwarzes Feld. Wenn wir nun bei einem Schachbrett zwei Felder von der Diagonale entfernen, bleiben insgesamt entweder noch 32 Weiße und 30 schwarze oder andersherum übrig. Da die Anzahl von schwarz [math] \neq [/math] weiß ist folgt daraus, dass das Brett nicht vollständig belegt werden kann. Demnach, wie wir schon wissen, am Ende zwei Felder der gleichen Farbe übrig bleiben.

Abgeschnittene Schachbretter

Aztekenfelder verschiedener Größe

Wir betrachten beim Arctic Circle Theorem oder dem Aztek Diamond nun Schachbretter bei denen nicht nur 2 Felder entfernt wurden, sondern im allgemeinen n((n/2)-1) Felder an allen vier Ecken entfernt wurden, sodass eine Raute entsteht. Somit hat das Feld nur noch n((n/2)+1) Feldern. Die Felder haben dann folgendes Aussehen:

Feldgröße 2 x 2 besteht aus 2 schwarzen 2 weißen Feldern
Feldgröße 4 x 4 besteht aus 6 schwarzen 6 weißen Feldern
Feldgröße 6 x 6 besteht aus 12 schwarzen 12 weißen Feldern
Feldgröße 8 x 8 besteht aus 20 schwarzen 20 weißen Feldern
...
Feldgröße n x n (n>2) besteht aus n((n/2)+1)/2 schwarzen und n((n/2)+1)/2 weißen Feldern.

Auch hier bestehen die Felder aus jeweils gleichvielen verschiedenfarbigen Feldern, da sonst die Überdeckung mit Dominosteinen nicht möglich ist, wie oben Bewiesen.

Pfade über das Schachbrett

Die Felder des Brettes, dem Aztekenfeld, werden durch das Überlegen des Brettes mit den Dominosteinen eingefärbt. Eingefärbt wird dabei so, dass die Farben festgelegt werden, je nachdem wo das weiße und wo das schwarze Feld ist. Im allgemeinen lässt sich sagen, dass es zwei Arten von Dominosteinen gibt, die Liegenden und die Stehenden. Zu den Liegenden gehören blau und grün, zu den Stehenden rot und gelb. Die Frage die man sich jetzt also stellen kann ist, ob es einen Weg über das Aztekenfeld gibt bei dem nur auf einer Art von Dominos (liegend oder stehend) entlanggegangen werden kann.

Ein möglicher Weg über ein 18 x 18 Feld

Doch gibt es immer einen Weg? Eine Vorüberlegung, die man sich machen kann ist, dass Dominosteine die stehen entweder oben oder unten schwarz haben, die die liegen rechts oder links. Außerdem können Dominosteine nur zwei benachbarte Felder belegen. Somit ist nach jedem neuen oder nächsten schwarzen Feld entweder ein stehender oder liegender Stein. Also mit [math]50\%[/math] Wahrscheinlichkeit sind zwei benachbarte gleich, und dass nicht nur nach links und rechts sondern auch oben und unten. Demnach hat ein Stein in der Mitte [math](1/2)^4[/math] Wahrscheinlichkeit dass alle Felder um ihn der gleichen Art sind. Um einmal von links nach rechts oder oben nach unten zu laufen brauchen die entsprechenden Steine in den Ecken also mindestens n Steine um dies zu schaffen.

Also ergibt sich daraus, da die Ecken schon solche der passenden Art sind und mindestens zwei Seiten eines Dominos mit der selben Art belegt werden muss, dass [math](n-2) * (0,5^2 + 0,5^3 + 0,5^4) * (Anzahl tilings) = 1[/math]

Die Monsterformel

Abbildung 1: Bestimmung der möglichen Belegungen

Diese Formel wurde 1961 von Piet Kasteleyn entwickelt und beschreibt die Anzahl der möglichen Belegungen eines rechteckigen n x m Schachbrettes.

[math]m\times\ n=\ \prod_{j=1}^\frac{m}{2}\prod_{k=1}^\frac{n}{2}\left(4\cos^2{\frac{j\pi}{m+1}}+4\cos^2{\frac{k\pi}{n+1}}\right)[/math]

falls m oder n ungerade sind, wird der dazugehörige Bruch [math]\frac{m}{2}[/math] oder [math]\frac{n}{2}[/math] aufgerundet.

Beispiel der Anwendung dieser Formel anhand eines 2 x 4- Schachbretts:

[math]2\times\ 4=\ \prod_{j=1}^\frac{2}{2}\prod_{k=1}^\frac{4}{2}\left(4\cos^2{\frac{j\pi}{2+1}}+4\cos^2{\frac{k\pi}{4+1}}\right)[/math]

[math]2\times\ 4=\ \prod_{j=1}^{1}\prod_{k=1}^{2}\left(4\cos^2{\frac{j\pi}{3}}+4\cos^2{\frac{k\pi}{5}}\right)[/math]

Nach Auflösen der Produkte ergibt sich folgender Term:

[math]\left(4{cos}^2{\frac{1\pi}{3}}+4{cos}^2{\frac{1\pi}{5}}\right)\left(4{cos}^2{\frac{1\pi}{3}}+4{cos}^2{\frac{2\pi}{5}}\right) = {5}[/math]

Wenn m und n ungerade Zahlen sind, so hat auch das Schachbrett eine ungerade Anzahl an Feldern und kann deshalb nicht gekachelt werden. Die Formel ergibt für diesen Fall immer den Wert 0.

Nun wird die Funktionsweise dieser Formel anhand eines Prinzips verdeutlicht, welches nicht nur für rechteckige Schachbretter, sondern allgemein gültig ist. Hier muss lediglich die Anzahl der schwarzen und weißen Felder identisch sein.

In Abbildung 1 ist ein zufälliges und nicht rechteckiges Schachbrett dargestellt. Zunächst werden, zur Bestimmung der Anzahl der möglichen Belegungen, die schwarzen und weißen Felder durchgezählt. Die Reihenfolge der Zahlen spielt hierbei keine Rolle. Anschließend werden alle direkt aneinander liegenden Zahlen in der nebenstehenden Tabelle markiert. Diagonal zueinander befindliche Zahlen sind hierbei ausgeschlossen. Alle in Verbindung stehenden Zahlen werden mit 1 markiert. Sind die beiden Zahlen identisch, so werden sie in der Tabelle mit der imaginären Zahl i versehen.

Die entstandene Tabelle kann nun direkt in eine Matrix übernommen werden, aus deren Determinante man die Anzahl der möglichen Belegungen des Schachbrettes ablesen kann.

Abbildung 2: Mögliche Belegungen

[math]\det \left(\begin{matrix}i&1&0&0&0\\1&i&1&0&0\\0&1&i&1&1\\0&0&0&i&1\\1&0&0&0&i\\\end{matrix}\right) = {3i}[/math]

Das Vorzeichen und die imaginäre Zahl i sind bei den jeweiligen Ergebnissen zu vernachlässigen. Somit beträgt die Anzahl der möglichen Tilings hier 3. Die unterschiedlichen Möglichkeiten in diesem Beispiel werden in Abbildung 2 dargestellt.

Berechnet man die mögliche Anzahl an Belegungen der [math]2\times\ n[/math]-Schachbretter in aufsteigender Reihenfolge, so erhält man die Fibonacci Folge.

[math][/math]

Aztekendiamant und "Arctic Circle"-Theorem

In der kombinatorischen Mathematik bestehen Aztec-Diamonds der Kardinalität (Ordnung) n aus allen Quadraten, deren Zentrum (x,y), die Gleichung [math]|x|+|y|\lt =n[/math] erfüllen. Die Anzahl wie oft man ein Aztec-Diamond der Ordnung n legen kann ist [math]2^{\frac{n(n+1)}{2}}[/math]. Das Theorem sagt nun, dass wenn n größer wird, die Ecken des Diamonds in einer Farbe sind und sich in der Mitte ein perfekter Kreis bildet. Jedes Domino wird genau ein schwarzes und ein weißes Feld treffen. Die Farben werden dann so festgelegt, je nachdem ob rechts, links oder oben, unten weiß oder schwarz ist.

Tanzende Dominosteine

Square Dance

Um einen Aztekendiamanten zu erhalten gibt es verschiedene Methoden. Zum Beispiel könnten viele Diamanten in der gewünschtn Größe erstellt werden, und jeden dieser Diamanten mit einer möglichen Kombination an Dominosteinenen bedecken, sodass alle möglichen Kombinationsmöglichkeiten einmal vorkommen. Aus dieser Menge könnte dann ein zufälliger Aztekendiamant gezogen werden. Das Problem ist, das diese Methode sehr (rechen-)aufwendig ist.

Eine bessere Methode ist die sogenannte Square-Dance-Methode. Hierbei werden ausgehend vom einfachsten Diamanten (A(1), ein 2x2 Quadrat) schrittweise beliebig große Aztenkendiamanten aufgebaut. Hierbei werden den Farben jeweils eine Richtung zugeordnet.

Square-Dance-Algorithmus:

2x2 Diamant zufällig mit zwei Dominosteinen belegen
Den Diamant um eine Ordung erweitern
Prüfen ob zwei Felder aufeinander zeigen, da hier kein Verschieben möglich wäre, diese Felder entfernen.
Die Dominosteine in die zur Farbe gehörige Richung verschieben
Die resultierenden 2x2 Felder zufällig belegen
zurück zu Schritt 2 gehen.

Anhand dieses Vorgehens ist es recht einfach zu sehen wie der Arctic Circle und vor allem die stabilen Ecken entstehen.

Arktischer Kreis und stabile Ecken

Fall 1. rechts und Fall 2. links

Es ist erstaunlich zu sehen, wie trotz des von Anfang an zufälligen Vorgehen, ein Aztekendiamant mit einigen sehr stabilen und geordeneten Regionen entsteht. Das erste Merkmal ist schon nach nur wenigen Iterationen sichtbar, nämlich die stabilen Ecken. Diese Struktur entsteht, da eine Ecke, z.B. oben, entweder:

mit zwei Dominosteinen, die nach rechts und links zeigen ausgefüllt ist, oder
mit einem nach oben zeigendem Stein.

Im ersten Fall, entseht im nächsten Iterationsschritt in der oberen Ecke ein freies 2x2 Feld, was wieder entweder mit 1. oder 2. gefüllt wird. Im zweiten Fall jedoch verschiebt sich dieser Stein jedoch nach und sitzt wieder in der oberen Ecke. Da in Fall 1. die Wahrscheinlichkeit für beide Fälle 50/50 ist, wird irgendwann Fall 2. eintreten. Dieser Stein blockiert dann dauerhaft die obere Ecke. Das selbe Prinzip sorgt dafür, dass unterhalb dieser Spitze sich nach und nach ein immer größer werdendes Feld an gleichen Steinen ansammelt. Dies gilt natürlich für alle Ecken, sodass das charateristisches "Eis" in den Ecken entsteht.

Diese stabile Verschieben in die Ecken sorgt außerdem für einen weiteren Effekt, nämlich dass in der Mitte des Diamanten ein Kreis von ungeordneten Dominosteinen entsteht. Dies ist der Arktische Kreis, der Namensgeber des Arctic Circle Theorem.

//Hier kommt noch ein Bild eines großen Diamanten//

[math] [/math]

Anzahl der Überdeckungen

Nachdem wir nun den Tanz der Dominosteine verstanden haben, wollen wir nun die Anzahl der Überdeckungen für einen beliebigen Aztekendiamant [math] A(n)[/math]berechnen. Wir beginnen mit [math] A(1)[/math]und sehen ein, dass es für diesen genau zwei Überdeckungen gibt. Ausgehend von einer dieser Möglichkeiten schieben wir nun im erweiterten [math] A(2)[/math]die Dominosteine in die durch den Pfeil angezeigte Richtung. Es bleiben nun zwei 4x4 Felder frei, die auf [math] 2^2[/math]Weisen überdeckt werden können. Dies ist das zentrale Argument im rigorosen Beweis der Aussage. Es kann nämlich analog zu unseren Überlegungen gezeigt werden, dass im k-ten Schritt [math] 2^{k}[/math]Möglichkeiten hinzukommen. Insgesamt erhalten wir also für den [math] A(n)[/math] genau [math] 2^{1} \cdot 2^{2} \cdot ... \cdot 2^{n} = 2^{1 + 2 + 3 + ... + n} = 2^{\frac{n(n+1)}{2}}[/math] mögliche Überdeckungen.

Anwendungen in der Physik und Weiterführendes

Atomare Gitter

Quellen

Teil 1:

Sciencia, Librero, ISBN: 978-90-8998-430-2, Seite 14f.
Fermats letzter Satz, Simon Singh, dtv, ISBN: 978-3-423-33052-7, Seite 44-50

Weiterführende Literatur

unfertig

Es wird untersucht wie man Domino-Fliesen einer Familie von endlichen Regionen namens Aztekendiamanten legen kann. Jedes Domino hat eine Farbe das in eines der fünf Unterregionen liegt; in den vier äußeren Teilregionen wird jede Kachel mit nahegelegenen Kacheln ausgerichtet, während im fünften, zentralen Teilbereich unterschiedlich ausgerichtete Kacheln nebeneinander existieren. Es wird gezeigt dass, wenn n ausreichend groß ist, die Form des zentralen Teilbereichs willkürlich einem perfekten Kreis des Radius n/sqrt(2) für alle außer einem vernachlässigbaren Anteil der Fliesen nahe kommt. (Random Tiligs Beschreibung)

Die Formeln sind (in Abschnitt 1) nicht aus dem Internet sondern selbst hergeleitet... könnten somit falsch sein. Die Formeln scheinen aber im allgemeinen richtig zu sein, da diese auch in den Artikeln in anderer Art aber so vom Ausdruck gleich aussehen.

Die Anzahl der Überdeckungen beträgt Bn=Fn. Wobei Fn die n-te Fibonaccizahl ist [1]. Dabei ist z.B. B0 = 2 x 0 also 1. Durch Induktion lässt sich nun beweisen, dass IA: B1 = 2 x 1 also F1=1 ist. IS: Wegen der Anzahl der Überdeckungen für Bn=Fn, folgern wir daraus Bn+1. Es gibt zwei Arten wie wir mit dem Überdecken beginnen können. Wir können mit einer horizontalen oder einer vertikalen Überdeckung beginnen. Beim horizontalen haben wir Bn, mit Fn verschiedene Überdeckungen, übrig. Beim Vertikalen Bn-1 mit Fn-1 verschiedenen Überdeckungen. Wenn wir diese zwei nun zusammenfügen erhalten wir für die Anzahl der Überdeckungen: B_n+1=Fn+Fn-1=Fn+1

Kommentar: Scheint irgendwie trivial Gemacht zu sein (Wurde von Wikipedia übernommen) (Anmerkung Steven: Das ist glaube ich die Formel für 2xn Bretter und nicht für die Azteken-Diamanten.)