Aufteilen eines Kuchens
- Autor:
- Alexander Thaller
Problemstellung
Ein großer Kuchen soll der Reihe nach entsprechend den folgenden Regeln auf 100 Personen aufgeteilt werden:
Die erste Person bekommt 1% des ganzen Kuchens.
Die zweite Person bekommt 2% des verbleibenden Kuchens (also ohne dem Stück der ersten Person).
Die dritte Person bekommt 3% des verbleibenden Kuchens.
Usw. bis die hundertste Person 100% des restlichen Kuchens erhält.
Als wievielte Person sollte man an der Reihe sein, um das größtmögliche Kuchenstück zu ergattern?
Lösung mit Technologieunterstützung
Die Aufgabe lässt sich gut mit einer Tabellenkalkulation lösen. Dazu formulieren wir das Problem in Form einer rekursiven Folge.
Sei der Anteil der Größe des verbleibenden Kuchens, nachdem Person ihr Stück bekam, bezogen auf die Anfangsgröße des Kuchens. Zum Beispiel bedeutet , nachdem die 8. Person ihr Stück bekam, sind noch 70% des anfänglichen Kuchens vorhanden.
Sei der Anteil der Größe eines Stückes, das Person bekommt, bezogen auf die Anfangsgröße des Kuchens. So bedeutet zum Beispiel , dass die 6. Person ein Stück erhält, welches 5% des Anfangskuchens entspricht.
Die rekursive Formulierung des Problems lautet dann für :
In der nachfolgenden Tabelle ist diese Rekursion dargestellt.
Im folgenden sieht man die grafische Darstellung, welche Person welche Stückgröße erhält. Man erkennt sehr schön das Maximum bei .
Wir haben also somit unsere Antwort gefunden:
Die 10. Person erhält das größte Stück vom Kuchen.
Rechnerische Lösung ohne Technologie
Wie würden wir das Problem ohne Rechnerunterstützung lösen?
Die Idee besteht wieder darin, das Problem in eine rekursive Form zu bringen. Diesmal aber nicht als zwei gekoppelte rekursive Folgen, sondern als eine einzige Folge für die Größe der Kuchenstücke . Die Lösung erhalten wir dann als den größten Wert bis zu dem die Folge monoton wächst.
Um den rekursiven Folgenterm(wir wären übrigens auch mit einem expliziten, wenn dieser einfacher zu entdecken ist zufrieden) zu finden, bestimmen wir die ersten Folgenglieder und versuchen ein Muster zu erkennen. Wir nehmen an dass der ganze Kuchen die Größe 1 hat.
In rekursiver Darstellung lautet die Folge also
Um herauszufinden für welche diese Folge monoton steigend ist, lösen wir die Ungleichung .
Das größte welches diese Ungleichung erfüllt ist . Daraus folgt, dass das letzte Verhältnis größer eins ist.
Somit schließen wir, dass das Maximum darstellt und die 10. Person das größte Stück am Kuchen erhält.
Dies stimmt natürlich mit der oben gefundenen Lösung überein.