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.
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).