Dodekaeder    MB Matheblog # 27 Inhalt Blog
voriger Eintrag    nächster Eintrag
zur Leitseite
Index der gesamten Website


2023-06-25


Ein Tortenproblem                    Kommentare sind willkommen.
Unter den Hunderten mathematischer Probleme, denen ich begegnet bin und die ich zum Teil in der Problem-Rubrik auf dieser Website vorgestellt habe, sind einige wenige, die zu meinen klaren Favoriten zählen. Ich mag Probleme, die einen gewissen "Pfiff" haben oder ein "Aha-Erlebnis" beim Leser hervorrufen, und auch solche, die verblüffend oder gar paradox erscheinen. All diese Eigenschaften finden sich in dem Tortenproblem, das hier behandelt werden soll. Unter meinen Favoriten steht es seit längerem an der Spitze (gefolgt vom Mauerschatten-Blog # 3).

Das Tortenproblem hätte auch in der Problem-Rubrik erscheinen können, aber ich habe mich für den Blog entschieden, weil die Lösung nicht ganz einfach ist.

Zuerst soll die Ausgangslage des Problems und das einfachste Beispiel beschrieben werden:
Bild 1 Eigene Torte
Tortenproblem  –  Einführung

Wir nehmen eine kreisrunde Torte mit einer dunklen Oberfläche (z.B. Schokolade) und einem hellen Boden. Aus ihr werden Tortenstücke gleicher Größe in Form von Kreissektoren ausgeschnitten (siehe Bild 1). Jedes Stück grenzt an seinen Vorgänger und liegt im Gegenuhrzeigersinn neben ihm.

Wenn ein Stück ausgeschnitten ist, wird es umgedreht, ändert also seine Farbe (siehe Bild 1). Der Einfachheit halber werden wir nicht immer von Dunkel und Hell, sondern meist von Schwarz und Weiß sprechen.

Zur Standardisierung dieses Vorgangs stellen wir uns vor, dass die Schnitte nicht gesetzt werden, indem jemand mit dem Messer um die Torte herumgeht, sondern die Schnitte werden immer am oberen Kreisrand angesetzt und der Kuchen wird im Uhrzeigersinn weitergedreht.

Mit Ausnahme des allerersten Schnitts ("Schritt 0", der im Folgenden bedeutungslos ist und nicht mitgezählt wird) soll ein "Schritt" aus drei Aktionen bestehen:

- Drehen der Torte um einen Winkel  α
- Schneiden
- Wenden des eben abgeschnittenen Tortenstücks

Im einfachsten Fall ist  α = 360°/m  mit natürlichem  m  2 .  Dann lassen sich genau  m  Stücke ohne Rest aus der Torte schneiden. Für  m = 9  zeigen wir mehrere Einzelschritte:

1/9 Schritte 0/1

Bild 2   α = 360°/9 = 40°

Was in Bild 2 gezeigt wurde, ist im Folgenden für beliebige Winkel  α  das Ziel: Es soll solange gedreht, geschnitten und gewendet werden, bis die Torte auf der Oberfläche wieder ganz dunkel ist.  Für  α = 360°/m  werden  s = 2m  Schritte benötigt.

Natürlich stellen sich sofort interessante Fragen: Geht das immer? Wieviel Schnitte werden benötigt?


Wenn die Tortenstücke einen Winkel  α  360°/m  haben, gibt es bei der Überschreitung des Vollkreises eine "Überlappung", die wir uns etwas genauer anschauen wollen:


Bei  α  360°/m  ist alles anders !

Wir zeigen in Bild 3 oben den "Überlappungs"-Schritt und unten den Folgeschritt sowie einen weiteren, willkürlich herausgegriffenen Schritt.

3/17
Bild 3   α = 360°·3/17

Was sieht man in Bild 3?
  • Die Torte lässt sich nicht ohne Rest in ganze Stücke schneiden; als Beispiel haben wir hier Tortenstücke genommen, deren Größe  3/17 der Gesamtfläche beträgt.

  • Dies führt zu einem ganz anderen Bild als in Bild 2. Nach dem 5. Schritt bleibt ein Reststück stehen, das kleiner als die bereits abgeschnittenen Stücke ist; den zugehörigen Winkel wollen wir  β  nennen. Also entsteht beim Drehen um den Winkel  α  eine "Überlappung". Nach dem Schneiden sehen wir noch einen dritten Winkel  γ .

  • Offenbar gilt für  α  = 360°·q  ( q  kein Stammbruch):
    β  =  360°-  1/q·α  =  360°-  n·α .  ( ⌊.⌋  steht für ganzzahlige Abrundung.) Hier haben wir  n = 1/q  gesetzt.  n  ist dann die Anzahl der Tortenstücke, die maximal aus der Torte geschnitten werden können, mit dem Reststück mit Winkel  β .  Damit gilt  360°/(n+1) <  α < 360°/n .  In Bild 3 ist also  β = 360°·2/17  und  n = 5 .

  • Wir erhalten  γ = α - β ,  also in Bild 3  γ = 360°·1/17 .

  • Der Schritt 7 wurde aufgenommen, um zu zeigen, wie es weitergeht  –  nämlich mit "Lücken" zwischen den schwarzen Flächen, was in Bild 2 nicht vorkam.  –  Schritt 15 zeigt zum einen, dass der Winkel  α  völlig verschwunden ist und nur noch  β  und  γ  vorkommen; und zum zweiten, dass es nicht ganz leicht ist sich vorzustellen, welche Flächen schwarz bzw. weiß nach  j  Schritten sind.
Führt das Verfahren für  α = 360°·3/17  zum "Erfolg" (Torte ganz dunkel)? Ja, und zwar nach  s = 60  Schritten. Das werden wir weiter unten noch beweisen. Ich denke, nur ganz Gewitzte erkennen jetzt schon, wie  s = 60  aus  q = 3/17  folgt.


An dieser Stelle möchte ich kurz innehalten. Das Tortenproblem habe ich schon häufiger vor Mathematikerinnen und Mathematikern präsentiert. Nach dem Beispiel mit  q = 3/17  höre ich mir gerne an, was die Fachleute glauben, wie es jetzt weitergeht. Hier kommen die interessantesten Antworten:


Was sind die üblichen Reaktionen, wenn die Lösung noch nicht verraten wurde ?
  • Hier ist die häufigste Einschätzung: Für rationale  q  kehrt man nach endlich vielen Schritten zum Ausgangszustand zurück. Für irrationale  q  ist das unmöglich.
    Die Begründung liegt auf der Hand: Für rationale  q  trifft man nach endlich vielen Schritten wieder auf eine bereits benutzte Schnittlinie. In unserem Beispiel mit  q = 3/17  trifft man im  17.  Schritt beim Schneiden auf den Randpunkt der Torte, an dem der allererste Schnitt durchgeführt wurde (Schritt 0).  –  Für irrationale  q  schneidet man dagegen nie zweimal an derselben Stelle.

  • Es gibt aber auch einen Einwand: Möglicherweise trifft man bei rationalem  q  nach endlich vielen Schritten wieder eine bereits benutzte Schnittlinie, die zu einem "Loop" führen könnte, der beliebig oft durchlaufen wird, ohne zum Anfangszustand zurückzukehren.

  • Sehr verbreitet ist die Einschätzung, dass für den Fall des "Erfolgs" (Torte wieder ganz dunkel) nach der Hälfte der Schritte die Torte ganz hell ist, also vollständig umgedreht. Dahinter steht ein Symmetriegedanke: Ganz Schwarz nach ganz Schwarz führt über ganz Weiß, wie in Bild 2 nach Schritt 9.

  • Für rationale  q  wird vermutet, dass die Abhängigkeit der Schrittzahl  s  vom Winkel der Tortenstücke zwar nicht leicht erkennbar ist, aber  s  mit der Größe des Nenners von  q  (maximal gekürzt) monoton wächst. Auch bei diesem Gedanken steht Bild 2 Pate. Demnach ist zu vermuten, dass beispielsweise  s  für  q = 3/17  kleiner ist als für  q = 611/929 .


Nun ist das Problem wohl ausreichend dargestellt worden. Wir wenden uns der Lösung zu.

Zunächst soll untersucht werden, wo genau die Schnittlinien liegen. Die Schwarz-Weiß-Färbung wird also erstmal weggelassen, ihr widmen wir uns später.

Bild 4 zeigt die ersten acht Schritte für  q = 5/24 .  In den ersten vier Schritten werden  α-Stücke ausgeschnitten; es bleibt ein Rest, nämlich ein  β-Stück mit  β = 360°- α·⌊1/q⌋ .  In den nächsten vier Schritten werden sukzessive die  α-Stücke durch je ein  β-  und ein  γ-Stück ersetzt (im Uhrzeigersinn), mit  γ = α - β .

75 ohne Farben
Bild 4   α = 360°·5/24 = 75°, n = 4

Nun sind wir bereits  –  obwohl wir nur ein Beispiel mit einem konkreten  q  gezeigt haben  –  an der entscheidenden Erkenntnis angelangt:

Den wesentlichen Erkentnisschritt haben wir am Beispiel  n = 4  vollzogen. Im vierten Spiegelpunkt des vorigen Abschnitts ist aber bereits die Verallgemeinerung auf beliebige  n  enthalten. Das Wesentliche soll nochmal wiederholt werden: Nach  2n  Schritten erhalten wir ein Schnittmuster mit den Winkeln  j·α, j = 0 ... n  und  j·α - γ, j = 1 ... n .  Dieses bleibt bei allen weiteren Schritten unverändert, wie die folgende Tabelle 1 zeigt; in Bild 6 werden diese Muster für  n = 1 ... 6  dargestellt.

  Nach  r  Schritten,  r  2n Drehen um  α Wenden Nach  r+1  Schritten
Winkel für Schnittlinien  
j·α , j = 0 ... n

---------------------------

j·α - γ , j = 1 ... n
j·α , j = 1 ... n

          γ         →
----------------------
j·α - γ , j = 2 ... n

 
 
α - γ
 
j·α , j = 0 ... n



j·α - γ , j = 1 ... n

Tabelle 1


n=1..6

Bild 6   Schnittmuster-Fixpunkte nach  2n  Schritten,  n = 1 ... 6

Bisher haben alle Bilder nur Winkel  α = 360°·q  gezeigt, für die  γ < β  ist. Damit lassen sich die Rechenschritte am besten in den Graphiken nachvollziehen. Aber diese Einschränkung ist natürlich unnötig, da sie in allen bisherigen Ausführungen keine Rolle spielte. In Bild 7 kann man zum Vergleich  γ = β  und  γ > β  sehen.

n=1..6

Bild 7   n = 4;  q = 5/24 (→ β > γ),  q = 2/9 (→ β = γ),  q = 117/500 (→ β < γ)


Zusammenfassung: Lage der Schnittlinien

α = 360°·q, q ∈(0,1)α  ist der Zentriwinkel der Tortenstücke.

Der triviale Fall:  q = 1/m, m  N, m  2    m  Schnittlinien bei  α·j/m, j = 0 ... m-1  (entspricht den Schritten  0 ... m-1 ) .

Der nichttriviale Fall:  q  kein Stammbruch,  n = 1/q, 360°/(n+1) <  α < 360°/n

  2n+1  Schnittlinien bei Winkeln  j·α, j = 0 ... n  und  j·α - γ, j = 1 ... n  (entspricht den Schritten  0 ... 2n ).

  n+1 β- Winkel,  n γ-Winkel .

Sobald alle diese Schnitte vorliegen, bleibt das Schnittmuster in allen weiteren Schritten identisch erhalten.


Nun zum letzten Teil, dem Farbwechsel Schwarz/Weiß. Wir wissen jetzt, dass für alle folgenden Überlegungen der genaue Wert des Winkels  α  keine Rolle spielt, sondern nur das zugehörige  n .  Zunächst schauen wir uns an, wie der Farbwechsel in einem konkreten Beispiel aussieht. In Bild 8 ist  n = 3 ;  wir erhalten das endgültige Schnittmuster mit  2n+1 = 7  Schnittlinien nach  2n = 6  Schritten (2. Zeile, linke Graphik); dabei zählt die erste, ganz schwarze Graphik nicht mit, sie steht für Schritt 0. Wir zählen  s(4) = 24  Schritte, bis die Torte wieder ganz dunkel ist.

n=3 mit Farben

Bild 8   n = 3


Bild 8 zeigt ein wesentliches Phänomen: An keiner Stelle ist die Torte ganz hell; damit ist wieder eine Vermutung aus den "Üblichen Reaktionen" (s.o.) widerlegt. Ist das immer so, oder hängt das evtl. von  n  ab? Es ist auch noch offen, ob man überhaupt für jedes  n  in endlichen vielen Schritten zum Ziel kommt, und ob es vielleicht "Loops" in der Abfolge der Farbbelegung gibt.

Wie hängt die erforderliche Anzahl der Schritte  s(n)  von  n  ab? Wir behandeln nur den nichttrivialen Fall, d.h.  q  ist kein Stammbruch.

Zusammenfassung: Farbwechsel; Anzahl der Schritte bis zum Ziel

α  Zentriwinkel der Tortenstücke.

Der triviale Fall:  α = 360°/m, m  N, m    s(m) = 2m  Schritte.

Der nichttriviale Fall:  360°/(n+1) < α < 360°/n    s(n) = 2n(n+1) Schritte.

     Die Folge  s(n) findet man in der Datenbank OEIS unter A046092.

     Ganz hell wird die Torte nie.


Damit ist alles gezeigt. Im Kasten mit den "üblichen Reaktionen" weiter oben hat sich also lediglich die Einschätzung bestätigt, dass  s(n) für rationale  q  endlich ist. Alles andere lag zwar intuitiv nahe, hat sich aber als falsch erwiesen.


Zum Schluss nochmal alles Wesentliche

Erstaunlich, aber wahr: Jede beliebige Größe der Tortenstücke (mit Winkel  α ) führt in endlich vielen Schritten zurück zum Ausgangszustand einer ganz dunklen Torte. Der Grund dafür  –  bei irrationalen Winkeln  –  liegt in der Verlagerung je einer Schnittlinie bei jedem Wenden eines Tortenstücks.

Ganz einfach ist das natürlich für  α = 360°/m :  m  Schnittlinien,  2m  Schritte, Torte ganz hell nach  m  Schritten.

Interessant ist nur der Fall  360°/(n+1) <  α < 360°/n .  Schon wenn man zweimal rundum geschnitten hat, ist ein konstantes Schnittmuster entstanden, so dass ab dann nicht mehr geschnitten, sondern nur noch gedreht und gewendet werden muss.

Das Schnittmuster hat dann  2n+1  Schnittlinien. Das Ziel wird nach  2n(n+1) Schritten erreicht, ohne dass die Torte auf diesem Weg ganz hell wird.

Die Anzahl der erforderlichen Schritte hängt also nicht davon ab, wie "kompliziert"  α  gewählt wird; insbesondere kann  α  ein irrationaler Bruchteil von  360° sein.

Woher stammt dieses Problem?  Das ist nicht bekannt; man weiß weder, wie alt es ist noch wer es ersonnen hat (mein Kenntnisstand  –  nach einiger Recherche  –  von 2022-03-29). Es ist Peter Winkler zu verdanken, dass er das Problem in seinem Buch  Mathematical Mind-Benders  vorgestellt hat. Er hat es aus einer französischen Quelle, weiß aber auch nichts Weiteres über seine Geschichte.



Kommentare sind willkommen.



Stand 2022-03-29


Inhalt Blog   |    voriger Eintrag   |    nächster Eintrag


Manfred Börgens   |   Zur Leitseite