Grenzen des Parkettierens

Von Thilo / 22. Februar 2019 / 11 Kommentare

Beim Parkettieren möchte man eine Fliese komplett mit identischen Fliesen umgeben. Mit den umgebenden Fliesen möchte man das dann wiederholen, und das noch möglichst oft.

Es gibt Fliesen (wie das Quadrat oder das regelmäßige Sechseck), mit denen man das unendlich oft wiederholen kann. Bei vielen Fliesen wird man aber nach endlich vielen Schritten nicht mehr weiterkommen. (Und es gibt natürlich viele Figuren, die man nicht einmal einmal mit identischen Stücken umgeben kann.) Die Anzahl der Schritte, wie oft man die Fliesenmuster fortsetzen kann, bezeichnet man als Heesch-Zahl der Fliese.

Es gibt Fliesen mit den Heesch-Zahlen 1 bis 5:

und man vermutet, dass sich das noch weiter fortsetzen läßt, es also zu jeder Zahl eine Fliese mit der entsprechenden Heesch-Zahl gibt. ~~Zum Beispiel vermutet man, dass diese Fliese die Heesch-Zahl 4622 hat:~~

Alles über Heesch-Zahlen und die damit zusammenhängenden Probleme erfährt man im neuen Video von Numberphile:

Kommentare (11)

#1 grilly
22. Februar 2019

Ich habe das numberphile-Video gestern gesehen.
Das mit 4622 war nur als Symbolbild gemeint.
Die Annahme war, dass es für jede Zahl eine passende Form mit der entsprechenden Heesch-Zahl geben soll.
Es sind aber bisher keine Formen mit Heesch höher als 5 bekannt und man hat auch noch keine Ahnung wie man das Problem effektiv angehen könnte.
Daher ist “Zum Beispiel vermutet man, dass diese Fliese die Heesch-Zahl 4622 hat:” leider falsch.
#2 Christian
22. Februar 2019

Ein sehr interessantes Video, Danke!

Eine kleine Anmerkung hätte ich: Wenn ich das Video richtig verstanden habe, dann zeigt das Bild keine Fliese mit der Heesch-Zahl 4622, weil man bisher ja noch nicht über 5 gekommen ist. Das soll viel mehr nur veranschaulichen, dass es womöglich eine Fliese gibt, die man in ganz vielen Ringen zusammenlegen kann. In dem Bild ist die Fliese gar nicht zu sehen, nur die vielen Ringe in Gruppen eingefärbt (die Fliese, wenn man ihre Form denn wüsste, wäre ja eh viel zu klein um sie zu sehen).
#3 Thilo
22. Februar 2019

Danke, ist jetzt durchgestrichen.
#4 Ingo
22. Februar 2019

Achtung: Hie spricht der Mathematik-Leihe.

Ich glaube das ganze ist ein Kapitel zum Thema Packing-Probleme
Packing-Probleme scheint ein Themenbereich der vielen Lieblingsprobleme der Mathematiker zu sein, und ich kann auch verstehen warum.
Es hat zum Beispiel im Bereich der Codierung von Daten konkrete Anwendungsszenarien.

Was mich aber interessieren wuerde:
Wie sind die Methoden um solche Dinge auszuarbeiten.

Beipiel:
Ich kann mir schwer vorstellen, dass es eine Funktion gibt
f(h) = Form der Fliese mit Heesch-Numer h
wo h die Heesch-Number ist, und das Ergebniss der Funktion eine Fliesenform ist.
Wenn es eine solche Funktion gäbe, waere ja auch alles ganz einfach.

Ich kann mir aber auch nicht vorstellen, dass ein Mathematiker einfach den ganzen Tag lang Fliesen vor sich hin zeichnet, bis er zufällig die richtige Fliese findet.

Wie werden solche Probleme abstrahiert betrachtet ?
Ich kann mir nochnichteinmal vorstellen wie man ein solches Problem abstrakt und mathematisch beschreibt – obwohl es eigentlich (in natuerlicher Sprache) relativ einfach zu verstehen ist.
Gibt es bestimmte Schreibweisen?
#5 ralph
23. Februar 2019

Das Problem erinnert mich sehr entfernt an den “gefangenen Springer”.
https://scienceblogs.de/mathlog/2019/01/25/der-gefangene-springer/
Auf dem Schachbrett entsteht durch den Weg des Springers ein Muster, welches sich in der Ebene ausbreitet und sich tendenziell vom Ausgangspunkt konzentrisch entfernt. Dabei gibt es für den Springer zunehmend weniger Optionen, bis er irgendwann eingesperrt ist. Das sieht man zwar kommen, aber es ist nicht klar, wann und warum es überhaupt passiert.
#6 Christian2
23. Februar 2019

Ist im Bild zu Heesch Number 5 ein Fehler? Ziemlich mittig oben grenzt ein rotes Feld direkt an ein gelbes. Normalerweise sollte doch aber eine grüne Fliese da anschließen? Die an das gelbe Feld angrenzende rote Fliese sollte grün eingefärbt sein, dann paßt das Bild.
#7 alex
23. Februar 2019

@Ingo:
Naja, eine solche Funktion gibt es schon (jedenfalls definiert auf den Zahlen, für die es eine Fliese mit dieser Heesch-Zahl gibt). Allerdings kennt man kein Verfahren um eine solche Funktion zu berechnen (bis auf die oben angegebenen Fälle h=0 bis h=5 und h=∞). In der Mathematik beinhaltet der Begriff “Funktion” nicht, dass man ein Verfahren zu ihrer Berechnung angeben können muss.

Was die formal-mathematische Beschreibung des Problems angeht: Auf der englischen Wikipedia-Seite https://en.wikipedia.org/wiki/Heesch%27s_problem gibt es dazu einen Abschnitt.

Und bezüglich der Vorgehensweise (bevor ich das Video gesehen hatte, kannte ich die Heesch-Zahlen nicht; also besteht das Folgende nur aus Mutmaßungen):

Zunächst stellt sich die Frage, wie man die Heesch-Zahl einer gegebenen Fliese überhaupt bestimmt.

Es dürfte vergleichsweise einfach sein, eine untere Schranke für die Heesch-Zahl zu finden (so lange diese endlich ist): Man legt einfach drauf los, bis man nicht mehr weiter kommt. Und wenn man das ausreichend oft auf unterschiedliche Weise macht, bekommt man eine Vermutung, wie die Heesch-Zahl lauten könnte.

Aber es dürfte im Allgemeinen schwierig sein, zu beweisen dass es keine Anordnung mit einer größeren Zahl an Schichten gibt. Man sieht zwar leicht, ob sich zu einer gegebenen Anordnung noch außen Fliesen hinzufügen lassen, aber vielleicht hat man weiter innen schon einen Fehler gemacht?

Deshalb bietet es sich an, sich auf solche Fliesen zu konzentrieren, bei denen dieser Schritt einfacher ist. Im Video wird kurz angesprochen, dass das bei der Fliese mit Heesch-Zahl 3 der Fall ist (weil für jede Fliese die konvexe Wölbung einen kleineren Winkel hat als die konkaven Wölbungen zusammen). Auf dieser Webseite https://www.ics.uci.edu/~eppstein/junkyard/heesch/ wird für eine andere Fliese ein ähnliches Argument vorgestellt.

Man könnte also versuchen, gezielt Fliesen (oder besser noch Familien von Fliesen) zu konstruieren, für die man ein solches Argument anwenden kann. Ich würde vermuten, dass die im Video gezeigten Fliesen mit Heesch-Zahl 4 und 5 auch so konstruiert wurden.

Auch ist klar, dass eine Fliese gewisse Bedingungen erfüllen muss, damit mit ihr überhaupt lückenlos parkettiert werden kann. Sonst hat man die selbe Situation wie beim Kreis mit Heesch-Zahl 0. Bei einem Polygon muss es z.B. für jeden Innenwinkel andere Innenwinkel geben, die sich mit diesem auf 360° summieren. Und auch die Längen der Seiten müssen geeignet zusammenpassen.

Aber zumindest zu Beginn wird man in der Tat sehr viel herumprobieren müssen.
#8 rolak
23. Februar 2019

Fehler?

Gut gesehen, Christian2, doch sooo einfach paßts nach der 1-Kachel-Umfärbung auch nicht – wohl deswegen ist in ENwiki eine völlig andere Parkettierung eingebunden.
#9 HF(de)
23. Februar 2019

Wenn man die gelbe Fliese, die an die rote stößt, grün einfärbt, passt es. Die gelbe ist falsch. s. https://faculty.washington.edu/cemann/Heesch.pdf
#10 rolak
24. Februar 2019

die gelbe

Ah, das Problem auf einer tiefergehenden Ebene gelöst, HF(de) – gespiegelt & gedreht und zack, sahs mir völlig anders aus…
#11 user unknown
https://demystifikation.wordpress.com
25. Februar 2019

Mich begeistern die Geräusche beim Ausfüllen der Fläche, die die Teile erzeugen. 🙂