Ein Rezept fürs Kuchenschneiden
Im Artikel Kuchengerechtigkeit in $n$ Dimensionen stellte ich ein Computerprogramm vor, dass alle Möglichkeiten findet, um in $n$ Dimensionen einen rechtwinkligen Kuchen in gleich viele ebenso rechtwinklige Rand- und Mittelstücke zu teilen. Randstücke sind solche, die man von außen sieht, Mittelstücke sind alle anderen. Geschnitten wird dabei immer durch den ganzen Kuchen und in jeder Dimension mindestens einmal.
Was aber ist, wenn man bei der Zubereitung des Kuchens gerade keinen Computer zur Hand hat? Auf dieser Seite leite ich eine Lösung her, die immer klappt.
Kuchenstückzahlen
Bezeichnet man mit $c_k$ die Anzahl der Schnitte in der $k$-ten von $n$ Dimensionen, dann beträgt die Anzahl der Mittelstücke:
Ohne Beschränkung der Allgemeinheit sei dabei festgelegt: $c_k\leq c_{k+1}$. Die Zahl der Randstücke lässt sich als Differenz aus der Gesamtzahl der Kuchenstücke und der Anzahl der Mittelstücke berechnen:
Gleichung aufstellen
Wir interessieren uns dafür, wann gleich viele Mittel- und Randstücke entstehen. Dafür setzen wir beide Zahlen gleich:
Nun soll die Gleichung etwas umgestellt werden. Auf beiden Seiten addiere ich noch einmal die Anzahl der Mittelstücke und erhalte:
Als nächstes teile ich beide Seiten der Gleichung durch $(c_n-1)\prod_{k=1}^{n-1}(c_k+1)$. Um keine Division durch null zu verursachen, sei $c_n>1$ vereinbart. Diese Vereinbarung schränkt uns nicht wirklich ein, da wir sowieso mehr als einen Schnitt je Dimension benötigen, um zahlenmäßige Gleichheit bei Rand- und Mittelstücke zu erreichen. Wir erhalten Gleichung A:
Wohlgemerkt, diese Gleichung gilt nicht immer, sondern genau dann, wenn gleich viele Rand- und Mittelstücke entstehen. Wir suchen Werte für $c_1$ bis $c_n$, die diese Gleichung lösen.
And now for something completely different?
An dieser Stelle möchte ich die Aufmerksamkeit auf einen anderen Ausdruck lenken:
Um nicht Gefahr zu laufen, durch null zu dividieren, sei dabei $a_1>2$ festgelegt. Was können wir nun mit dem Ausdruck anfangen? Wir können die Zähler und die Nenner jeweils ausmultiplizieren und zusammenfassen, um den Ausdruck auf einen Bruchstrich zu bringen:
Wir können einen Trick anwenden und einen neuen Namen vergeben: $a_2:=a_1^2-a_1$. Wenn wir den auf der rechten Seite in Zähler und Nenner einsetzen, erhalten wir Gleichung B:
Wie man wiederum durch Ausmultiplizieren und Zusammenfassen überprüfen kann, gilt aber auch:
und wenn wir den Namen $a_3:=a_2^2-a_2$ vergeben, haben wir:
Den ersten Bruch auf der linken Seite jener Gleichung können wir mithilfe von Gleichung B auch ersetzen, um dies zu erhalten:
Mit $a_{k+1}:=a_k^2-a_k$ ist allgemein:
und es gilt mit wiederholtem Einsetzen für den ersten Bruch auf der linken Seite Gleichung C:
Wohlgemerkt, diese Gleichung gilt mit den vorgenommenen Definitionen immer!
Lösung
Nun gilt es zu ernten, was gesät wurde. Dafür ist nur noch eine Festlegung zu treffen: $a_1:=4$. Wenn wir dies in Gleichung C einsetzen und die rechte Seite ein wenig umformulieren, erhalten wir:
Die strukturelle Übereinstimmung mit Gleichung A zeigt, dass wir eine Lösung für Gleichung A gefunden haben! Die Werte für $c_1$ bis $c_{n-1}$ entsprechen dabei $a_1$ bis $a_{n-1}$ und ergeben sich aus der Festlegung $a_1:=4$ zusammen mit der Bildungsvorschrift $a_{k+1}:=a_k^2-a_k$.
$k$ | 1 | 2 | 3 | 4 | 5 | … |
---|---|---|---|---|---|---|
$a_k$ | 4 | 12 | 132 | 17292 | 298995972 | … |
Das ist Folge A204321 in der OEIS. Zu guter Letzt ist $c_n=a_n-1$.
Wenn wir beispielsweise einen Kuchen in drei Dimensionen in gleich viele Rand- und Mittelstücke schneiden wollen, geht das mit 4 Schnitten in der Breite, 12 in der Höhe und 131 Schnitten in der Tiefe.