Satz von Kawasaki - Kawasaki's theorem
Der Satz von Kawasaki ist ein Satz in der Mathematik des Papierfaltens , der die Faltmuster mit einem einzelnen Scheitelpunkt beschreibt , der gefaltet werden kann, um eine flache Figur zu bilden. Es besagt, dass das Muster genau dann flach faltbar ist, wenn abwechselndes Addieren und Subtrahieren der Winkel aufeinanderfolgender Falten um den Scheitelpunkt eine abwechselnde Summe von Null ergibt . Faltmuster mit mehr als einem Scheitelpunkt erfüllen ein so einfaches Kriterium nicht und sind NP-schwer zu falten.
Der Satz ist nach einem seiner Entdecker, Toshikazu Kawasaki, benannt . Einige andere trugen jedoch auch zu seiner Entdeckung bei, und es wird manchmal nach anderen Mitwirkenden, Jacques Justin und Kôdi Husimi, als Kawasaki-Justin-Theorem oder Husimis Theorem bezeichnet .
Aussage
Ein Ein-Scheitel- Knickmuster besteht aus einer Reihe von Strahlen oder Knicken, die auf ein flaches Blatt Papier gezeichnet werden und alle von demselben Punkt im Inneren des Blatts ausgehen. (Dieser Punkt wird als Scheitelpunkt des Musters bezeichnet.) Jede Falte muss gefaltet werden, aber das Muster gibt nicht an, ob die Falten Bergfalten oder Talfalten sein sollen . Ziel ist es festzustellen, ob es möglich ist, das Papier so zu falten, dass jede Falte gefaltet wird, an anderer Stelle keine Falten entstehen und das gesamte gefaltete Blatt Papier flach liegt.
Um flach zu falten, muss die Anzahl der Falten gleich sein. Dies folgt beispielsweise aus dem Satz von Maekawa , der besagt, dass sich die Anzahl der Bergfalten an einem flach gefalteten Scheitel von der Anzahl der Talfalten um genau zwei Falten unterscheidet. Nehmen wir daher an, dass ein Faltenmuster aus einer geraden Anzahl von 2 n von Falten besteht, und seien α 1 , α 2 , ⋯, α 2 n die aufeinanderfolgenden Winkel zwischen den Falten um den Scheitelpunkt herum im Uhrzeigersinn, beginnend bei einem von die Engel. Dann besagt der Satz von Kawasaki, dass das Faltenmuster genau dann flach gefaltet werden kann, wenn sich die abwechselnde Summe und Differenz der Winkel zu Null addiert:
- α 1 − α 2 + α 3 − + α 2 n − 1 − α 2 n = 0
Eine äquivalente Möglichkeit, dieselbe Bedingung anzugeben, besteht darin, dass, wenn die Winkel in zwei abwechselnde Teilmengen unterteilt werden, die Summe der Winkel in jeder der beiden Teilmengen genau 180 Grad beträgt. Dies gilt jedoch nur äquivalente Form auf ein Faltmuster auf einem flachen Stück Papier, während die alternierende Summe Form der Bedingung für die Knittermuster auf konische Blätter Papier mit ungleich Null gültig bleibt Defekt am Scheitelpunkt.
Lokale und globale Flachfaltbarkeit
Der Satz von Kawasaki, der auf jeden der Eckpunkte eines beliebigen Faltmusters angewendet wird, bestimmt, ob das Faltmuster lokal flach faltbar ist , was bedeutet, dass der Teil des Faltmusters in der Nähe des Eckpunktes flach gefaltet werden kann. Es gibt jedoch Faltmuster, die lokal flach faltbar sind, aber keine globale Flachfaltung aufweisen, die für das gesamte Faltmuster auf einmal funktioniert. Tom Hull ( 1994 ) vermutete, dass die globale Flachfaltbarkeit getestet werden könnte, indem man den Satz von Kawasaki an jedem Scheitelpunkt eines Faltmusters überprüft und dann auch die Zweiteiligkeit eines ungerichteten Graphen testet, der dem Faltmuster zugeordnet ist. Diese Vermutung wurde jedoch von Bern & Hayes (1996) widerlegt , die zeigten, dass Hulls Bedingungen nicht ausreichend sind. Noch stärker zeigten Bern und Hayes, dass das Problem des Testens der globalen Flachfaltbarkeit NP-vollständig ist .
Beweis
Um zu zeigen, dass Kawasakis Bedingung notwendigerweise für jede flach gefaltete Figur gilt, genügt es zu beachten, dass bei jeder Faltung die Orientierung des Papiers umgekehrt wird. Wenn also die erste Falte in der flach gefalteten Figur in der Ebene parallel zur x- Achse liegt, muss die nächste Falte um einen Winkel von α 1 gedreht werden, die darauffolgende Falte um einen Winkel von α 1 − α 2 (weil der zweite Winkel die umgekehrte Ausrichtung zum ersten hat) usw. Damit das Papier im endgültigen Winkel wieder auf sich selbst trifft, muss die Kawasaki-Bedingung erfüllt sein.
Um zu zeigen, dass die Bedingung auch eine ausreichende Bedingung ist, muss beschrieben werden, wie ein bestimmtes Faltmuster so gefaltet wird, dass es flach gefaltet wird. Das heißt, man muss zeigen, wie man wählt, ob man Berg- oder Talfalten macht und in welcher Reihenfolge die Papierklappen übereinander angeordnet werden sollen. Eine Möglichkeit besteht darin, eine Zahl i zu wählen, so dass die partielle alternierende Summe
- α 1 − α 2 + α 3 − ⋯ + α 2 i − 1 − α 2 i
ist so klein wie möglich. Entweder i = 0 und die Teilsumme ist eine leere Summe , die ebenfalls Null ist, oder für eine von Null verschiedene Wahl von i ist die Teilsumme negativ. Dann falten Sie das Muster mit einem Akkordeon, beginnend mit dem Winkel α 2 i + 1 und abwechselnd zwischen Berg- und Talfalten, wobei Sie jeden Winkelkeil des Papiers unter die vorherigen Falten legen. Bei jedem Schritt bis zur letzten Falte wird sich eine Akkordeonfalte dieser Art niemals selbst überschneiden. Die Wahl von i stellt sicher, dass der erste Keil links von allen anderen gefalteten Papierstücken herausragt, sodass der letzte Keil wieder daran angeschlossen werden kann.
Mit einem alternativen Suffizienznachweis kann gezeigt werden, dass es viele verschiedene flache Faltungen gibt. Betrachten Sie den kleinsten Winkel α i und die beiden Knicke auf beiden Seiten davon. Falten Sie eine dieser beiden Falten bergwärts und falten Sie die andere talwärts, wobei Sie willkürlich wählen, welche Falte für welche Falte verwendet werden soll. Kleben Sie dann die resultierende Papierlasche auf den restlichen Teil des Faltmusters. Das Ergebnis dieser Verklebung ist ein Knickmuster mit zwei Knickfalten weniger auf einem konischen Blatt Papier, das noch immer dem Kawasaki-Zustand entspricht. Daher führt die Wiederholung dieses Prozesses durch mathematische Induktion schließlich zu einer flachen Faltung. Der Basisfall der Induktion ist ein Kegel mit nur zwei Knicken und zwei gleichwinkligen Keilen, der offensichtlich flach gefaltet werden kann, indem man für beide Knicke eine Bergfalte verwendet. Es gibt zwei Möglichkeiten, um auszuwählen, welche Falten in jedem Schritt dieser Methode verwendet werden sollen, und jeder Schritt beseitigt zwei Falten. Daher hat jedes Faltenmuster mit 2 n Falten, das die Bedingung von Kawasaki erfüllt, mindestens 2 n verschiedene Auswahlmöglichkeiten von Berg- und Talfalten, die alle zu gültigen flachen Falten führen.
Geschichte
In den späten 1970er Jahren beobachteten Kôdi Husimi und David A. Huffman unabhängig voneinander, dass flach gefaltete Figuren mit vier Knicken entgegengesetzte Winkel haben, die zu π addieren , ein Spezialfall von Kawasakis Theorem. Huffman nahm das Ergebnis 1976 in eine Arbeit über gekrümmte Falten auf, und Husimi veröffentlichte den Vierfaltensatz in einem Buch über Origami-Geometrie mit seiner Frau Mitsue Husimi. Das gleiche Ergebnis wurde noch früher in zwei Aufsätzen von S. Murata aus dem Jahr 1966 veröffentlicht, die auch den Sechsfalten-Fall und den allgemeinen Fall des Maekawa-Theorems enthielten .
Die Tatsache, dass Faltenmuster mit beliebig vielen Falten notwendigerweise abwechselnde Winkelsummen haben, die sich zu π addieren, wurde von Kawasaki, von Stuart Robertson und von Jacques Justin (wiederum unabhängig voneinander) in den späten 1970er und frühen 1980er Jahren entdeckt. Wegen Justins Beitrag zum Problem wurde der Satz von Kawasaki auch Kawasaki-Justin-Theorem genannt. Dass diese Bedingung ausreichend ist, d. h. dass Faltenmuster mit gleichmäßig vielen Winkeln, die sich abwechselnd zu π summieren, immer flach gefaltet werden können, mag erstmals von Hull (1994) festgestellt worden sein .
Kawasaki selbst hat das Ergebnis nach Kôdi Husimi als Satz von Husimi bezeichnet, und einige andere Autoren sind dieser Terminologie ebenfalls gefolgt. Der Name "Theorem von Kawasaki" wurde diesem Ergebnis erstmals in Origami for the Connoisseur von Kunihiko Kasahara und Toshie Takahama gegeben (Japan Publications, 1987).
Hull (2003) schreibt die untere Schranke von 2 n der Anzahl unterschiedlicher flacher Faltungen eines Faltenmusters, das die Bedingungen des Theorems erfüllt, der unabhängigen Arbeit von Azuma, Justin und Ewins und Hull in den frühen 1990er Jahren zu.
Obwohl der Satz von Kawasaki die Faltungsmuster mit flach gefalteten Zuständen vollständig beschreibt, beschreibt er nicht den Faltprozess, der erforderlich ist, um diesen Zustand zu erreichen. Bei einigen Faltmustern kann es erforderlich sein, das Papier zu krümmen oder zu biegen, während es von einem flachen Blatt in seinen flach gefalteten Zustand umgewandelt wird, anstatt den Rest des Papiers flach zu halten und nur die Flächenwinkel bei jeder Faltung zu ändern . Für starres Origami (eine Art der Faltung, die die Oberfläche mit Ausnahme der Falten flach hält, geeignet für scharnierte Platten aus starrem Material anstelle von flexiblem Papier) sind zusätzliche Bedingungen für ein Faltmuster erforderlich, damit es aus einem ungefalteten Zustand in einen a flach gefalteter Zustand.