Proportionales Cake-Cutting

Wie teilt man einen Weihnachtsstollen fair auf?

Heute möchten wir uns mit einem, gerade zur Weihnachtszeit, wichtigen Problem befassen, das gar nicht so ganz einfach zu lösen ist: Wie teilt man einen Kuchen, beispielsweise einen Stollen, fair unter beliebig vielen Personen auf, so dass jeder mit seinem Stück zufrieden und nicht neidisch auf einen anderen ist?

Tatsächlich ist "faires Teilen" eine mathematische Disziplin, die versucht, derartige Probleme durch Modellierung und intelligente Rechenschritte zu lösen. Wir möchten Euch hier kurz und verständlich erläutern, wie das sogenannte Proportional Cake-Cutting-Problem mit einem einfachen Algorithmus zu lösen ist. 

Ausgangssituation

Die Geschwister Anna und Tim wollen sich einen Weihnachtsstollen teilen und diesen in zwei faire Stücke teilen. Der Weihnachtsstollen hat eine unregelmäßige Form, so dass die Mitte nicht unmittelbar erkennbar ist. Wie gehen sie nun am besten vor, so dass jeder ein Stück bekommt, mit dem er sich nicht benachteiligt fühlt?

Personen
2

Teilen durch drei Personen

Noch bevor Anna und Tim ihre Idee in die Tat umsetzen können, kommt mit Max eine dritte Person hinzu. Er möchte ebenfalls ein Stück des Stollens haben und die drei beschließen, den Stollen fair auf drei Personen aufzuteilen.

Personen
3

Beliebig viele Personen n

Die oben dargestellte Vorgehensweise ist für beliebig viele Personen erweiterbar.
Gehen wir nun davon aus, dass wir nicht nur zwei oder drei Personen, sondern eine beliebige aber feste Anzahl n von Personen haben, unter die der Weihnachtsstollen fair aufgeteilt werden soll.

Personen
n

Weiterführende Gedanken

Wir haben im letzten Szenario gesehen, wie man den Weihnachtsstollen unter beliebig vielen Personen fair aufteilen kann. Mathematiker und auch Informatiker machen sich jetzt auch noch Gedanken darüber, wie viele Kerben bei diesem Verfahren insgesamt gezogen werden. Diese Anzahl gibt Auskunft über die Laufzeit des Verfahrens. Wir können uns überlegen, dass bei n Personen

  • n Kerben gezogen werden müssen, um das erste Teilstück abzutrennen, dann
  • (n-1) Kerben, um das zweite Teilstück abzutrennen, dann
  • (n-2) Kerben, um das dritte Teilstück abzutrennen usw.
  • bis ganz zum Schluss noch 2 Kerben gezogen werden müssen, um den Stollen unter den verbliebenen zwei Personen aufzuteilen.

Insgesamt machen wir also  n + (n-1) + (n-2) + …. + 2 = ½ n (n+1) -1  viele Kerben. Die Anzahl der Kerben wächst damit quadratisch mit der Anzahl der Personen. Wollen bei einem Dorffest, wo ein riesiger Stollen von der ortsansässigen Bäckerei gebacken wurde, 1000 Leute ein faires Stück erhalten, müssten mit dem Verfahren mehr als eine halbe Millionen Kerben gezogen werden.

Es gibt auch ein anderes Verfahren zum fairen Teilen, das auf dem Prinzip „Teile und Herrsche“ beruht. Bei diesem Verfahren werden nur in der Größenordnung n log n viele Kerben gezogen. Das würde beim Dorffest die Anzahl der zu ziehenden Kerben auf ca. 10.000 reduzieren.

Haben wir Ihr Interesse geweckt?

Mathematik ist die Grundlage für jede technische Errungenschaft und ein unabdingbarer Baustein innovativer Themen. Wer in unserer heutigen schnelllebigen und komplexen Welt ein Mathematik Studium vorzuweisen hat, der ist gefragter denn je. Ob in der Finanzbranche, der Automobilindustrie, bei Unternehmensberatungen, in der Medizintechnik, der IT- und Telekommunikationsbranche oder im Maschinenbau: Mathematik ist ein Türöffner in nahezu jede Branche und eröffnet exzellente Chancen auf dem Arbeitsmarkt

Egal ob klassische oder kooperative Studienvariante: Wir bilden Sie an der HFT Stuttgart als strukturierten Problemlöser, mathematischen Kreativdenker und kommunikativen Teamplayer aus. Dafür stehen zwei Vertiefungsrichtungen zur Auswahl: Algorithm Engineering (informatischer Schwerpunkt) oder Finanz- und Versicherungsmathematik (wirtschaftsmathematischer Schwerpunkt).

Mehr über Mathe an der HFT
Veröffentlichungsdatum: 19. November 2020