Kuchengerechtigkeit in n Dimensionen
Wie man mehrdimensionale Blöcke in gleich viele Mittel- und Randstücke teilt

Wie man einen flachen Blechkuchen mit Schnitten in zwei Dimensionen in gleich viele Rand- und Mittelstücke teilt, erläuterte ich im Artikel Demografie der Blechkuchenstücke. Doch was ist, wenn man es mit mehrdimensionalem Kuchen zu tun hat? Wie teilt man zum Beispiel einen Kuchenblock in fünf Dimensionen so, dass sich weder Liebhaber von Randstücken noch Mittelstückanhänger benachteiligt fühlen? Ich zeige ein Python-Programm, das Schnittkombinationen mit Gleichverteilung findet.

Abbildung: Blockkuchenmodelle in drei Dimensionen: Der Block links besitzt 1 Mittel- und 26 Randstücke, jener hinten 8 Mittel- und 56 Randstücke, jener rechts nur 8 Randstücke.
(Foto von Roland Frisch, www.rofrisch.de, GNU-Lizenz für freie Dokumentation, Version 1.2 oder später)

Wie beim klassischen Blechkuchen geht dabei jeder Schnitt durch den ganzen Kuchen. Alle Schnitte in einer Dimension sind zueinander parallel sowie rechtwinklig zu Schnitten in den anderen Dimensionen. In jeder Dimension wird mindestens einmal geschnitten.

Anzahl der Kuchenstücke

Wenn man mit ck die Anzahl der Schnitte in der k-ten von n Dimensionen bezeichnet, dann ergibt das Schneiden so viele Kuchenstücke insgesamt:

$$(c_1+1)(c_2+1)\cdots(c_n+1)$$

Mathematiker schreiben solche Produkte anstatt mit vagen Pünktchen gern mit einem großen griechischen Buchstaben Π als wohl definiertes Produktzeichen. So meinen die Schreibweisen links und rechts der Gleichung das gleiche:

$$(c_1+1)(c_2+1)\cdots(c_n+1)=\prod_{k=1}^n(c_k+1)$$

Stücke ohne außen liegende Seite heißen Mittelstücke. Ihre Zahl in beiden Schreibweisen:

$$(c_1-1)(c_2-1)\cdots(c_n-1)=\prod_{k=1}^n(c_k-1)$$

Wenn wir von der Gesamtstückzahl die Zahl der Mittelstücke abziehen, erhalten wir die Zahl der Randstücke:

$$\prod_{k=1}^n(c_k+1)-\prod_{k=1}^n(c_k-1)$$

Randstücke minus Mittelstücke

Nun stellen wir eine Formel für den Überschuss an Randstücken, dn genannt, auf. Dafür ziehen wir von der Anzahl der Randstücke die Anzahl der Mittelstücke ab. Diese Formel bekommt den schmucken Namen Formel A:

$$d_n=\prod_{k=1}^n(c_k+1)-2\prod_{k=1}^n(c_k-1)$$

Das Ziel ist klar: Wenn dn = 0 ist, also weder ein Überschuss noch ein Mangel an Randstücken besteht, ist die gesuchte Gleichverteilung von Rand- und Mittelstücken erreicht. Doch zunächst soll die Formel noch etwas manipuliert werden: Wenn man (cn + 1) und (cn − 1) aus den Produktdarstellungen „ausklammert“ …

$$d_n=(c_n+1)\prod_{k=1}^{n-1}(c_k+1)-2\,(c_n-1)\prod_{k=1}^{n-1}(c_k-1)$$

… kann man die Gleichung wie folgt umstellen:

$$d_{n}=\left(\prod_{k=1}^{n-1}(c_k+1)-2\prod_{k=1}^{n-1}(c_k-1)\right)c_n+\prod_{k=1}^{n-1}(c_k+1)+2\prod_{k=1}^{n-1}(c_k-1)$$

Das sieht zwar zunächst komplizierter aus. Allerdings fällt auf, dass der große Klammerausdruck bis auf den Unterschied, dass nun n − 1 statt n steht, der rechten Seite der Formel A entspricht und der letzte Summand hier bis auf denselben Unterschied dem Subtrahenden aus Formel A entspricht. Somit lässt sich die folgende Darstellung wählen, Formel B:

$$d_{n}=d_{n-1}(c_n-1)+2\prod_{k=1}^{n-1}(c_k+1)$$

Dies ist eine rekursive Definition: Der Überschuss in beispielsweise sechs Dimensionen wird mithilfe des Überschusses in den ersten fünf Dimensionen berechnet, dieser wiederum mithilfe des Überschusses in den ersten vier Dimensionen und so weiter. Als Anfangsbedingung sei d0 = −1 gegeben. Das folgende Programm beruht auf Formel B, wobei der Zusammenhang besonders in der dritten Programmzeile erkennbar sein mag.

Python-Programm

Das Programm findet und gibt in einer gegebenen Anzahl von Dimensionen alle möglichen Schnittkombinationen eines Kuchenblocks aus, bei denen gleich viele Rand- und Mittelstücke entstehen und $c_{n-1}\leq c_n$ gilt.

Die Bedingung $c_{n-1}\leq c_n$ hat den Zweck, nur wahrlich unterschiedliche Schnittkombinationen auszugeben, nicht mehrere Permutationen derselben. Ob ich einen Kuchen in zwei Dimensionen beispielsweise erst fünfmal in einer Richtung und dann siebenmal in der anderen schneide oder erst siebenmal in einer Richtung und dann fünfmal in der anderen, ist hier egal. Die Kombination wird nur einmal als [5, 7] registriert.

def find (dimensions):
    def findr (countdown, step, prod, cuts):
        diff = step * (cuts[-1] - 1) + prod
        if diff > 0:
            cuts[-1] -= diff // step
            diff %= step
        if countdown == 1:
            if diff == 0:
                print (cuts)
        else:
            if diff == 0:
                cuts[-1] += 1
                diff += step
            while cuts[-1] != findr (countdown - 1, diff, prod * (cuts[-1] + 1), cuts + [cuts[-1]]):
                cuts[-1] += 1
                diff += step
        return cuts[-1]
    if isinstance (dimensions, int) and dimensions > 0:
        findr (dimensions, -1, 2, [1])

Wenn Du alle Kombinationen in vier Dimensionen ausgegeben haben möchtest, forderst Du dazu so auf:

find (4)

Die eigentliche Arbeit macht die Funktion findr. Sie ist in die Funktion find eingekapselt, um einen einfachen Aufruf mit sinnvollen Parametern sicherzustellen. Beachte, dass die Rechenzeit und Anzahl der Lösungen mit der Zahl der Dimensionen schnell wächst. Bei sechs Dimensionen umfasst die Ausgabe des Programms gut 167 Megabytes.

Ergebnisse

In einer Dimension gibt es eine Lösung: [3]. Wenn man Beispielsweise einen Apfelstrudel dreimal quer schneidet, erhält man zwei Mittelstücke und genauso viele Rand- bzw. Endstücke. In zwei Dimensionen heißen die zwei Lösungen [4, 11], [5, 7]. Es gibt zwanzig Lösungen in drei Dimensionen, bereits 374 Lösungen in vier Dimensionen und 21313 Lösungen in fünf Dimensionen. In sechs Dimensionen gibt es 5115140 Lösungen. Wer möchte, findet die gut 167 Megabytes lange Liste der Schnittkombinationen unter folgender Adresse: https://prlbr.de/2015/mehrdimensional-kuchen-schneiden/6d.txt


Die Anfangsbedingung d0 = −1 ist nicht beliebig. Setzt man n = 0 in Formel A, haben die durch Π gekennzeichneten Produkte keine Faktoren. Man spricht von leeren Produkten, welchen sinnvoll der Wert 1 zugewiesen ist. Somit ergibt sich d0 = (1) − 2(1) = −1.