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. 

Personen
2

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
3

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
n

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.

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