Startseite → Matherätsel → Pizza teilen → Lösung

Lösung: Pizza teilen

Rätsel einblenden

Lösung

Ausblenden

Vorab: Die Lösung S(n) = 2n-1, die Sie vielleicht durch Ausprobieren herausbekommen haben, stimmt nur bis n = 5. Für n = 6 Markierungen entstehen aber höchstens 31 Pizzastücke. Die ersten Werte von S(n), die wir durch Ausprobieren herausfinden können, sind:

n 0 1 2 3 4 5 6 7
S(n) 1 1 2 4 8 16 31 57

Die Lösung dieses Problems ist wesentlich komplizierter als S(n) = 2n-1. Wir leiten zuerst eine Rekursionsformel für S(n) her. Dazu können wir davon ausgehen, dass wir die maximale Anzahl Stücke erhalten, wenn wir die Markierungen so setzen, dass sich nicht mehr als zwei Schnitte in einem Punkt kreuzen.

Wir nehmen nun an, dass wir die Lösung S(n-1) für (n-1) Markierungen bereits kennen und schließen daraus auf die Lösung S(n):

Skizze für (n-1) Markierungen

Fügen wir zu den bereits vorhandenen (n-1) Markierungen eine weitere Markierung hinzu, so erhalten wir (n-1) zusätzliche Schnitte:

Skizze für n Markierungen

Wir betrachten zuerst nur einen dieser „neuen” Schnitte: Den von der neu hinzugefügten Markierung n zu einer (beliebigen) Markierung k:

Wir betrachten vorerst nur einen Schnitt

Von jeder der Markierungen 1, …, (k-1) auf der „linken” Seite dieses Schnitts geht je ein Schnitt zu jeder der Markierungen (k+1), …, (n-1) auf der „rechten” Seite. Insgesamt gehen also (k-1) · (n-k-1) viele Schnitte „von links nach rechts”. Der „neue” Schnitt von n nach k muss jeden dieser Schnitte kreuzen. Jedes Mal, wenn der neue Schnitt von n nach k einen dieser Schnitte kreuzt, dann hat er gerade ein Pizzastück zweigeteilt. Zusätzlich teilt er noch ein weiteres Pizzastück, nämlich das, das k als einen Eckpunkt hat. Insgesamt bekommen wir durch den Schnitt von n nach k also

(k-1)\cdot(n-k-1)+1

zusätzliche Pizzastücke.

Bisher haben wir nur einen „neuen” Schnitt betrachtet. Wir müssen aber alle (n-1) „neuen” Schnitte von n nach 1, …, (n-1) betrachten. Insgesamt erhalten wir durch das Hinzufügen von Markierung n also

\sum_{k=1}^{n-1}\left((k-1)\cdot(n-k-1)+1\right)

zusätzliche Pizzastücke.

Außerdem hatten wir bereits S(n-1) Pizzastücke. Insgesamt muss also gelten:

S(n)=S(n-1)+\sum_{k=1}^{n-1}\left((k-1)\cdot(n-k-1)+1\right)

Da wir S(0) = 1 kennen, können wir mit dieser Formel sämtliche Werte S(n) für beliebige n rekursiv (also Schritt für Schritt) berechnen und haben das Problem damit gelöst.

Wir können dies über verschiedene Summenformeln und etwas Rechenaufwand aber auch noch umformen zu:

S(n)=S(n-1)+\frac{1}{6}\cdot(n-3)\cdot(n-2)\cdot(n-1)+n-1

Durch sukzessives Einsetzen der Formel für S(n-1), S(n-2), …, S(1) erhalten wir:

S(n)=\underbrace{S(0)}_{=1}+\sum_{k=1}^{n-1}\left(\frac{1}{6}\cdot(k-3)\cdot(k-2)\cdot(k-1)+k-1\right)

Dies können wir durch erneute Anwendung verschiedener Summenformeln und einigen Rechenaufwand zu einem Polynom umformen. Die Lösung unseres Problems lautet also in expliziter Form: Der Pizzabäcker kann durch das Setzen von n Markierungen an den Rand seiner Pizza maximal

S(n)=\frac{1}{24}\cdot{n^4}-\frac{1}{4}\cdot{n^3}+\frac{23}{24}\cdot{n^2}-\frac{3}{4}\cdot{n}+1

Pizzastücke bekommen. Diese Formel liefert tatsächlich genau die Werte in der oben aufgeführten Tabelle.