6.1.1.6.4 Mathematische Hintergründe
Parkettierung ganzzahliger Zwölfecke

Parkettierung ganzzahliger Zwölfecke

In diesem Kapitel beschäftigen wir uns mit Zwölfecken, deren Seiten ganzzahlige nicht negative Vielfache einer Kantenlänge a lang sind und die bzgl. ganzer Vielfacher von 120 Grad rotationssymmetrisch sind. Ist eine Kantenlänge gleich Null, so ist das Zwölfeck entartet.

Beispiele:

Beispiel a) ist ein reguläres gleichseitiges Zwölfeck mit Kantenlänge 1. Alle übrigen Zwölfecke haben Kantenlängen 1 oder 2 und sind entartet. Beispiel b) hat zwar auch zwölf Ecken, 3 davon fallen mit benachbarten Ecken zusammen und sind deshalb nicht sichtbar. Beispiele c) bis e) haben je nur 6 sichtbare Ecken und f) bis i) sogar nur je 3.

Wir können die Zwölfecke durch ihre Kantenlängen beschreiben. Beginnen wir mit der unteren waagerechten Kante gegen den Uhrzeigersinn, so kann a) beschrieben werden durch das Zwölftupel (1,1,1,1,1,1,1,1,1,1,1,1) und b) durch (2,1,0,1,2,1,0,1,2,1,0,1). Wegen der Rotationssymmetrie wiederholen sich die Zahlen in Gruppen von 4. Für eine Charakterisierung eines solchen Zwölfecks reichen somit 4 Zahlen, oder die Viertupel (1,1,1,1) für a) bzw. (2,1,0,1) für b).

Die Viertupel der Beispiele zeigt folgende Tabelle:

Sind alle zwölf Kantenlängen null, so haben wir sogar eine Entartung des Zwölfecks zu einem Punkt.

Wir interessieren uns in erster Linie dafür, ob und wie man solche Zwölfecke mit gleichseitigen Vierecken und gleichseitigen Dreiecken gleicher Basiskantenlänge parkettieren kann. Mit Ausnahme von c) geht dies bei allen unseren Beispielen. Bei g), h) und i) ist dies unmittelbar einsichtig, da die entarteten Zwölfecke bereits gleichseitige Dreiecke sind. Für d, e) und f) zeigen folgende Skizzen die Parkettierung.

Für c) haben wir ebenfalls eine Skizze mit dem Versuch einer Parkettierung. Die linke obere Ecke hat einen Winkel von 90 Grad. Hier passt nur ein Viereck hin. Nach dem Platzieren des Vierecks A entsteht darunter wieder ein Winkel von 90 Grad. Hier können wir ebenfalls nur ein Viereck platzieren, welches wir mit B bezeichnen. Darunter haben wir eine neue Ecke des entarteten Zwölfecks und es bleibt ein Winkel von 60 Grad, wo nur das mit C bezeichnete Dreieck passt. In die nächste Ecke des entarteten Zwölfecks passt nur wieder ein Viereck D. zwischen C und D bleibt ein Winkel von 30 Grad.

Da passen weder Viereck noch Dreieck. Die Platzierungen der Vierecke A, B, D und des Dreiecks C waren aber zwingend, so dass damit gezeigt ist, dass eine Parkettierung mit gleichseitigen Vierecken und Dreiecken bei diesem entarteten Zwölfeck nicht möglich ist.

Die Platzierung für das entartete Zwölfeck b) zeigt untenstehende Skizze. Hier haben wir es mit einer Mischung aus gleichseitigen Vierecken und Dreiecken zu tun.

Auch Beispiel a) lässt sich mit gleichseitigen Vierecken und Dreiecken parkettieren, wie links stehende Skizzen zeigen. Hier haben wir es offenbar mit zwei Möglichkeiten zu tun, wie man die gleichseitigen Vierecke und Dreiecke platzieren kann. Natürlich gehen beide Platzierungen durch Drehen des Zwölfecks um 30 Grad auseinander hervor, aber für unsere Belange sollen das wirklich zwei verschiedene Platzierungen sein.

Wir interessieren uns dafür, für welche Zwölfecke Parkettierungen von gleichseitigen Vierecken und Dreiecken existieren und wie viele es ggf. sind. Da wir keine Einschränkung bzgl. der Größe der Zwölfecke gemacht haben, können diese sehr groß werden. Vielleicht bekommt man einen Eindruck, wenn man versucht, sich ein Zwölfeck (47,13,25,30) vorzustellen. Natürlich könnten diese Zahlen auch in die Millionen oder Milliarden gehen.

Wir stellen hier eine Methode vor, wo wir diese Frage für beliebig große solche Zwölfecke relativ einfach beantworten können. Dazu betrachten wir noch einmal a) und b). Wir sehen, dass man die Platzierung in zwei Teile teilen kann. Zum einen in die Dreiecke und Vierecke, die direkt am Rand des Zwölfecks liegen und einem inneren Teil.

Für c) existiert solch eine Aufteilung offenbar nicht. Aber für alle Zwölfecke für die eine Parkettierung existiert. Lassen wir also vorerst alle Zwölfecke ohne Platzierung außen vor.

Was passiert, wenn wir solch eine Aufteilung vornehmen? Betrachten wir noch einmal die zugehörigen Viertupel bzw. zunächst mal die Zwölftupel. Für a) außen haben wir (1,1,1,1) oder (1,1,1,1,1,1,1,1,1,1,1,1), für a) innen (1,0,1,0) oder (1,0,1,0,1,0,1,0,1,0,1,0). Wir sehen, dass sich beim Übergang von außen nach innen jeder zweite Wert des Viertupels bzw. Zwölftupels um 1 reduziert. Das Gleiche gilt bei b) (2,1,0,1) bzw. (2,1,0,1,2,1,0,1,2,1,0,1) auf (2,0,0,0) bzw. (2,0,0,0,2,0,0,0,2,0,0,0).

Für die zweite Variante von a) wird (1,1,1,1) zu (0,1,0,1).

Ist also ein Zwölfeck durch (n_₁,n_₂,n_₃,n_₄) beschrieben und 0 < n_₁,n_₃ bzw. 0 < n_₂,n_₄, so wird das innere Zwölfeck durch (n_₁ - 1,n_₂,n_₃ - 1,n_₄) bzw. (n_₁,n_₂ - 1,n_₃,n_₄ - 1) beschrieben. Für entartete Zwölfecke ist mindestens eine der n_₁, n_₂, n_₃ oder n_₄ gleich 0. Damit ist eine Reduktion für diese Zwölfecke eindeutig. Für nicht entartete Zwölfecke teilt sich die Reduktion in zwei Varianten.

Für c) sieht man, dass wegen (0,0,2,2) keine der Reduktionen infrage kommt.

Nach einer Reduktion erhalten wir wieder ein Zwölfeck, welches man ggf. wieder reduzieren kann. Dies kann man solange wiederholen, bis n_₁=n_₂=0 oder n_₂=n_₃=0 oder n_₃=n_₄=0 oder n_₄=n_₁=0 sind. Es bleiben nur wenige Fälle übrig. (0,0,0,0), (0,0,0,n_₄), (0,0,n_₃,0), (0,n_₂,0,0) und (n_₁,0,0,0) mit n_₁,n_₂,n_₃,n_₄ > 0 ergeben Zwölfecke, die man parkettieren kann. (n_₁,n_₂,0,0), (0,n_₂,n_₃,0), (0,0,n_₃,n_₄) und (n_₁,0,0,n_₄) mit n_₁,n_₂,n_₃,n_₄ > 0 ergeben Zwölfecke, die man nicht parkettieren kann.

Das Zwölfeck (47,13,25,30) wird reduziert zu (22,0,0,27) und lässt sich deshalb nicht parkettieren. (47,30,25,30) wird dagegen reduziert zu (22,0,0,0) und kann parkettiert werden. Es fällt auf, dass mindestens n_₁ = n_₃ oder n_₂ = n_₄ erforderlich ist, damit das Zwölfeck parkettiert werden kann. Diese Bedingung ist sogar hinreichend.

Bleibt noch eine Frage.

Wenn es mindestens eine Parkettierung für ein Zwölfeck gibt, wie viele verschiedene gibt es?

Betrachten wir dazu noch einmal das Zwölfeck (n_₁,n_₂,n_₃,n_₄).

Seien m_₁ = MIN(n_₁,n_₃) und m_₂ = MIN(n_₂,n_₄). Seien weiter n_₁ = r_₁ + m_₁, n_₂ = r_₂ + m_₂, n_₃ = r_₃ + m_₃ und n_₄ = r_₄ + m_₄. Dann lässt sich das Zwölfeck darstellen durch (r_₁ + m_₁,r_₂ + m_₂,r_₃ + m_₃,r_₄ + m_₄) oder durch (r_₁,r_₂,r_₃,r_₄) + (m_₁,m_₂,m_₃,m_₄). Dabei sind r_₁ = 0 oder r_₃ = 0 und r_₂ = 0 oder r_₄ = 0.

Seien weiter x_₁ = MAX(r_₁,r_₃), x_₂ = MAX(r_₂,r_₄) und weiter x = MAX(x_₁,x_₂), y = MIN(x_₁,x_₂). Dann existiert eine Platzierung genau dann, wenn auch y = 0 ist. Damit bleibt für (r_₁,r_₂,r_₃,r_₄) nur eine der vier Möglichkeiten (x,0,0,0), (0,x,0,0), (0,0,x,0) oder (0,0,0,x).

(m_₁,m_₂,m_₁,m_₂) lässt sich durch Reduktion auf (0,0,0,0) reduzieren. Wir können auch (m_₁,m_₂,m_₁,m_₂) kürzer als (m_₁,m_₂) schreiben. Man kann zeigen, dass dann die Anzahl der Platzierungen gleich

Formel 22

Formel 22

ist.

Für Beispiel c) ist y = 2, also #p = 0.