Autor
Raimund Seidel, Universität des Saarlandes
![](/~algorithmus/Algorithmen/algo43/pictures/lightly_decorated_evergreen_01.png)
Die Tage nach Weihnachten sind am coolsten. Katja lungert auf dem Sofa und spielt mit ihren Haaren herum. Die Erwachsenen sind vom Weihnachtsstress ganz erschöpft und lassen einen in Ruh. Man muss nicht in die Schule, kann in der Früh ausschlafen und sonst faulenzen.
Stimmt, sagt ihr Bruder Holger, aber es wird auch schnell langweilig. Draußen nur Regenwetter. Fast alle Freunde im Urlaub. Was soll man denn da noch tun? Gut, dass wenigstens Gert noch da ist!
Gert hockt am Boden und arrangiert die Fransen am Teppichrand. Ja, sagt der, Schnee wäre wirklich besser als Regen. Was gibt's denn im Fernsehen?
Immer nur Fernsehen! Euch Jungs fällt auch nichts anderes ein. motzt Katja und ärgert sich still über die Bücher, die sie zu Weihnachten bekommen hat. Für Bibi Blocksberg ist sie nun ja wirklich schon zu alt.
Wo ist denn schon wieder die Fernbedienung? Holger sucht Tisch und Regal ab. Die kann doch nicht einfach weg sein!
Ich glaube, die ist in der Küche, meint schließlich Katja. Die liegt gleich neben dem Toaster.
Na, hoffentlich nicht im Toaster, murmelt Holger und geht in die Küche. Das wäre einmal was Neues.
Du, Katja, ruft er, was ist denn das für ein Kuchen auf dem Tisch?
Das ist der Pochelsteiner Weihnachtsstollen, von Tante Hedwig. Du weißt doch, sie bringt jedes Jahr einen.
Kuchen? stöhnt Gert und macht mit einer Handbewegung sein Teppichfransenarrangement kaputt. Jetzt, nach Advent und Weihnachten, mag ich schon das Wort kaum noch hören.
Nein, nein, Gert, sagt Holger und kommt mit einer Kuchenplatte zurück. Darauf liegt der ganze Stollen. Er ist nicht besonders groß, aber sieht appetitlich aus und verströmt einen feinen Duft. Nein, Gert. Tante Hedwigs Pochelsteiner Weihnachtsstollen ist was ganz Besonderes. Da hätte sich sogar die Prato noch was abschneiden können.
Wer, wie, was abschneiden? fragt Gert verwundert. Ach, ignorier ihn! rät Katja. Seitdem er im Sommer in Österreich war, redet Holger manchmal ganz wirres Zeug.
Die drei stehen um den Kuchen herum. Der Duft löst selbst bei Gert gewaltigen Kuchenhunger aus. Also sehr groß ist der ja leider nicht, meint Holger. Ein ordentliches Stück für jeden, und der ist weg. Er verschwindet in die Küche und kommt mit einem Messer zurück.
Holger, du hättest schon auch Kuchenteller mitbringen können, mahnt Katja vorwurfsvoll. Du weißt doch, wie fröhlich Mama wird, wenn wir hier im Wohnzimmer alles vollkrümeln.
Wir können ja nachher staubsaugen.
Du und staubsaugen! Das möchte ich sehen! schnaubt Katja und holt Kuchenteller.
Und wie kriegen wir den Kuchen in drei Teile? fragt jetzt Gert und greift sich an die Brille.
Ja mit dem Messer natürlich, antwortet Holger.
Nein, ich meine, wie kriegen wir ihn in drei gleich große Teile? Wir wollen doch fair teilen, oder?
Nach kurzer Stille sagt Katja: Wir könnten doch mit einem Zentimetermaß messen, wie lang der Stollen ist. Dann teilen wir das durch drei -- . Ach, ich sehe schon, das wird nichts. Der Stollen ist ja dünner an den beiden Enden und dicker in der Mitte.
Ja, aber wir könnten ein Waage verwenden, wirft Gert ein.
Und wie soll das helfen? fragt Holger. Wir schneiden den Stollen in drei Stücke und wägen sie? Die sind dann sicher nicht alle gleich schwer, also müssen wir vom schwersten Stück wieder etwas wegschneiden und an die anderen Stücke verteilen. Aber dann haben wir vielleicht zu viel weggeschnitten und wir müssen diesen Fehler korrigieren, was wieder zu einem neuen Fehler führt, und so fort. Am Schluss haben wir dann wahrscheinlich nur noch Krümel und keinen Kuchen. Schade um den guten Stollen!
Ja müssen denn die drei Teile wirklich genau gleich schwer werden? fragt Gert.
Natürlich! antwortet Holger. Wenn du wirklich fair teilen willst, dann müssen doch die drei Teile gleich schwer werden. Alles andere wäre doch unfair!
Unser alter Nachbar, beginnt Katja nach einiger Zeit, der Herr Maier, der hat mir einmal erzählt, wie er im Krieg lang mit einem Kameraden unterwegs war und sie nur mehr wenig zu essen hatten. Die haben ihr Brot dann immer so geteilt, dass der Eine das Stück in zwei Hälften geschnitten hat und der Andere sich dann die Hälfte ausgesucht hat. So musste sich der Eine beim Schneiden immer bemühen, möglichst gleich große Hälften zu erzeugen, weil ihm sonst nach der Wahl des Anderen nur die kleinere Hälfte übriggeblieben wäre.
Kleinere Hälfte! stänkert Holger, wenn unser Mathelehrer das hört, sagt er immer: `So ein Blödsinn! Es gibt keine kleinere Hälfte. Hälften sind per definitionen gleich groß!
Du weißt schon, was ich meine, antwortet Katja. Und übrigens heißt es per definitioneM korrigiert sie dazu.
DefinitioneM, DefinitioneN, DefinitionENG! Mir egal! entfährt es Holger. Schwesterchen, was soll denn diese Kriegsgeschichte überhaupt? Wir wollen doch den Stollen in drei Teile schneiden und nicht in zwei.
Aber vielleicht können wir diese Idee verwenden, wirft Gert ein. Ich könnte doch den Stollen in drei Stücke schneiden. Dann such Katja sich ein Stück aus, dann du, Holger, und ich muss das Stück nehmen, das übrig bleibt.
Klingt doch gut, sagt Katja.
Nein, nein, nein! erwidert ihr Bruder. Nehmen wir einmal an, Gert ist in dich verknallt. Dann schneidet er den Stollen in ein großes Stück und zwei kleinere. Du kannst dir dann das große Stück nehmen. Ich bekäme nur ein kleines, was mir gar nicht recht wäre. Und er kriegt natürlich auch nur ein kleines Stück; aber wenn er in dich verknallt ist, ist das dem galanten Helden ja egal. Hauptsache er hat dir ein großes Stück zugespielt.
Gert errötet unmerklich. Vielleicht sollte dann Holger zuerst ein Stück nehmen, nachdem ich geschnitten habe, meint er.
Und wie kann ich dann sicher sein, dass du nicht ihm ein großes Stück zuschanzst? Damit du dir seinen neuen Super-MP3-Spieler ausborgen kannst, oder sonst etwas?, erwidert Katja.
Vielleicht sollte Katja schneiden, und Holger nimmt sich als Erster ein Stück, dann ich und dann Katja, sagt Gert.
Aber dann bekommen wir doch nur die gleichen Misstrauensprobleme in grün, antwortet Holger, beziehungsweise in pink und schaut auf Katjas neuen Pullover. Diese Idee aus der Kriegsgeschichte funktioniert wohl nicht bei drei Leuten.
Die drei schweigen eine Weile und starren auf den Pochensteiner Stollen. Ich hab's! ruft Katja auf einmal. Wir bitten einfach Papa, dass er den Stollen möglichst fair in drei Stücke teilt.
Holger rollt die Augen: 'This is the dumbest thing I have ever heard!' würde da Bill Gates sagen. Papa würde doch wahrscheinlich zuerst für sich ein Stück abzweigen. Da kriegen wir dann alle weniger.
Da hast du auch wieder recht, sagt Katja kleinlaut.
Wieder ist es eine Zeit lang still. Dann sagt Holger: Jetzt krieg ich aber wirklich Hunger. Er fuchtelt mit dem Messer herum. Ich glaube, wenn ich hier abschneide, bekomme ich genau ein Drittel des Stollens. Er führt die Klinge zum Stollen, zieht sie noch einmal kurz zurück, setzt sie auf und möchte zu schneiden beginnen.
HALT!! rufen Katja und Gert wie aus einem Munde. Holger hält inne und zieht das Messer zurück. Eine deutliche Kerbe ist jetzt am Stollenrücken zu erkennen.
Das Stück wird doch zu groß, sagt Katja. Gib das Messer her! Ich glaube, ein Drittel des Stollens kriegst du genau hier! und ritzt den Kuchen fast einen Zentimeter näher am Ende.
Eigenartig, sagt Gert. Ich finde, dass Holger das Drittelstück zu klein machen würde. Ich würde hier abschneiden. Er nimmt das Messer und ritzt den Stollenrücken ein paar Millimeter näher zur Mitte von Holgers Kerbe aus gesehen.
Na toll!, klagt Katja. Drei Personen, drei Meinungen. So kommen wir nie auf einen grünen Zweig.
Ja, aber der Kuchen wird vielleicht noch grün vor Schimmel, bis wir uns da auf irgendetwas geeinigt haben, ätzt Holger.
Du bist ein Ekel, erwidert seine Schwester.
Ich hab's! Ich hab's, ich hab's! ruft auf einmal Gert. Die Geschwister schauen ihn verdutzt an. Wir schneiden den Stollen einfach irgendwo zwischen Katjas und Holgers Kerben. fährt Gert aufgeregt fort.
Und was soll das bringen? fragen die Geschwister.
Wir geben dieses Stück einfach Katja.
Aber dann bekommt sie doch mehr als ein Drittel des Stollens! ruft Holger empört.
Aus ihrer Sicht schon, antwortet Gert, und das wird sie wohl fair finden, oder, Katja? Sie nickt. Aus unserer Sicht bekommt sie aber weniger als ein Drittel. fährt Gert fort. Das heißt, aus unserer Sicht bleibt mehr als zwei Drittel des Stollens für uns beide übrig. Dieses große Stück können wir dann fair in zwei Hälften teilen, so wie es euer Maier-Nachbar im Krieg gemacht hat, und damit bekommt Holger und auch ich jeder ein Stück, das wir jeder für mehr als ein Drittel des Stollens halten. Das ist doch auch für uns fair, Holger, oder?
![](/~algorithmus/Algorithmen/algo43/pictures/stollencut.jpg)
Holger kratzt sich am Kopf und denkt nach. Das ist wirklich raffiniert, Gert sagt er schließlich. Jeder von uns macht eine Kerbe in den Kuchen, dort wo er glaubt, dass ein Drittel auf einer Seite der Kerbe liegen und zwei Drittel auf der anderen Seite. Bekommt er allein die Seite mit dem Drittel oder mehr, dann kann er happy sein, denn er hat mindestens so viel bekommen, wie er glaubt, dass ihm zusteht. Bekommt er mit einem andern zusammen die Seite mit den zwei Dritteln oder mehr, dann kann er auch happy sein, denn zu zweit haben sie mindestens soviel bekommen, wie sie glauben, dass ihnen zusammen mindestens zusteht. Sie müssen nur noch diesen gemeinsamen Teil fair in zwei Hälften teilen.
Und der Trick ist, dass durch den Schnitt zwischen der ersten und zweiten Kerbe jedem von uns einer der beiden Fälle beschert wird. Am Schluss bekommt dann sogar jeder von uns drei mehr, als er glaubt, dass ihm zusteht. Das grenzt schon an Zauberei!
Gert strahlt, stolz auf seine Idee. Es könnte aber auch sein, dass wir alle drei genau die gleiche Kerbe machen, wirft Gert ein. Dann bekommt keiner echt mehr, als er glaubt dass, ihm zusteht.
Richtig! sagt Katja. Kommt, lasst uns jetzt endlich den Stollen schneiden und essen!
Holger nimmt das Messer. Also wie war das? Ich muss zwischen der ersten und zweiten Kerbe irgendwo schneiden, vom Kuchenende gerechnet?
Ja, antwortet Katja, aber warte, ich glaube es hat an der Tür geläutet.
Sie springt auf und läuft aus dem Wohnzimmer. Kurz darauf kommt sie mit ihrer Cousine Sandra zurück.
Hallo Jungs!, tönt sie, und nachträglich fröhliche Weihnachten!
Hallo Sandra, grüßen sie zurück. Long time, no see.
Euer Englisch ist wirklich umwerfend. Oh, der Kuchen sieht aber gut aus. Krieg ich ein Stück?
Die drei schauen einander entgeistert an. Ach Sandra, sagt Katja schließlich, jetzt haben wir uns ganz schlau überlegt, wie wir den Stollen ganz fair in drei Teile schneiden können, so dass keiner glaubt, dass er zu kurz kommt, und jetzt platzt du herein.
Sandra schaut interessiert: Ganz schlau und ganz fair, in drei Teile? Erzählt einmal, wie geht das!
Katja legt los und erzählt ganz stolz die eben ausgeheckte faire Schnittmethode für drei. Sandra hört aufmerksam zu und ist beeindruckt. Und es bekommt wirklich jeder sogar mehr, als er glaubt, dass ihm zusteht?, fragt sie schließlich.
Wenn wir drei verschiedene Kerben machen, dann sicher, antwortet Katja. Aber jetzt ist das Ganze ja wertlos, denn jetzt sind wir vier, und wie man fair in vier Teile schneidet, das wissen wir nicht.
Noch nicht! Noch nicht! sagt Sandra. Aber ich glaube, ich weiß schon, wie man das machen könnte.
Erzähl! erwidern die drei erstaunt. Das ging ein wenig schnell.
Also, beginnt Sandra, es ist ja eigentlich ganz einfach.
Das sagt unser Mathelehrer auch immer, und dann kommt meist etwas ganz Unverständliches, bemerkt Gert.
Ganz Einfach Unverständlich? ergänzt Holger.
Genau! Ganz Einfach Unverständlich. blödelt Gert.
Also hört mal zu, fährt Sandra fort, es ist wirklich ganz einfach. Jeder von uns Vieren macht eine Kerbe in den Stollen, dort wo er glaubt, dass man genau ein Viertel des Stollens abschneiden würde. Und dann zählen wir vom Stollenende weg die Kerben, und zwischen der ersten und zweiten Kerbe machen wir einen Schnitt. Dieses abgeschnittene Stück bekommt dann der, der die erste Kerbe gemacht hat. Denn der bekommt dann mehr, als was er für ein Viertel hält, und das ist aus dessen Sicht wohl fair.
Das heißt, man muss sich merken, wer welche Kerbe gemacht hat? wirft Katja ein.
Natürlich! antwortet Sandra. Und für die anderen drei, die das erste Viertel nicht bekommen haben, erscheint es auch fair, denn aus deren Sicht wurde weniger als ein Viertel des Stollens weggeschnitten, es bleibt also mehr als drei Viertel übrig.
Was machen die dann mit den drei Vierteln oder mehr? fragt Holger.
Aber das ist doch jetzt klar, sagt Gert. Sie verwenden die faire Dreiteilungsmethode, die wir uns gerade ausgedacht haben, und teilen so die drei Viertel oder mehr, in dreimal jeweils ein Viertel oder mehr. Das ist ja wirklich einfach!
Am Schluss hat dann auch wieder jeder mehr als er glaubt, dass er eigentlich bekommen sollte. Das ist wirklich verrückt. ergänzt Katja.
Also kommt, lasst uns endlich diesen Weihnachststollen teilen und essen, bevor ihn die Ameisen davontragen. sagt Holger ungeduldig.
Das tun sie dann auch. Es dauert zwar eine Weile, bis da alles richtig, so wie geplant geteilt wird (und es würde auch schneller gehen, wenn sich Holger seine Kerben merken könnte), aber schließlich sitzt jeder bei seinem Stück Pochelsteiner Weihnachstsstollen aus Tante Hedwigs Küche und genießt.
Ich habe irgendwo gelesen, sagt Holger mampfend, dass sie in Erfurt oder so irgendwo einen ganz langen Weihnachtsstollen gebacken habe, zehn Meter waren es, glaube ich. Ob man den auch fair aufteilen kann? Auf, sagen wir, hundert Leute?
Du hast wieder Sorgen! sagt Katja.
Nein! Ich finde die Frage interessant, meint Sandra. Und ich glaube, ich weiß auch, wie man das machen kann, fährt sie fort, zumindest theoretisch.
Ohje. 'Theoretisch', wenn ich das schon höre!, stöhnt Katja. Und ich weiß auch gar nicht, wie du uns das heute noch erklären könntest. Bis du da jeden Schnitt für jedes der hundert Stücke erläutert hast, ist es ja schon nach Mitternacht.
Nein. Das kann ich schnell erklären. erwidert Sandra. Es ist ja auch wieder ganz einfach.
Ohja. sagt Gert aufgeregt. Ich glaube ich weiß auch, wie das gehen kann. Ich werd's erklären.
Aber fall doch Sandra nicht ins Wort, Gert! mahnt Katja.
Entschuldigung! murmelt der und schaut ein bisschen betroffen.
Also, beginnt Sandra, da haben wir den langen Stollen und hundert Leute. Jeder schaut sich den Stollen genau an und überlegt sich, wo er glaubt, dass man abschneiden müsste, um seiner Meinung nach genau ein Hundertstel des Stollens zu bekommen. Natürlich müssen die das alles vom gleichen Ende des Stollens aus tun. Dann macht jeder eine Kerbe in den Stollen und merkt sie sich.
Na toll, spottet Holger. Wie soll denn das gehen? Vor lauter Kerben wird der Stollen doch um die Stelle in Krümeln zerfallen, und keine Kerbe wird mehr sichtbar sein, ganz zu schweigen davon, wie man sich da seine Kerbe merken können soll.
Ja, ich weiß. sagt Sandra. Deswegen habe ich auch 'theoretisch' gesagt. Und außerdem könnten sie ja statt Kerben zu schneiden so Zahnstocherfähnchen an den entsprechenden Stellen in den Stollen stecken.
Da können sie gleich ihre Namen auf die Fähnchen schreiben, und keiner muss sich mehr was merken ergänzt Gert.
Richtig!, fährt Sandra fort. Jeder hat also sein Fähnchen in den Stollen gesteckt, dort wo er meint, dass der richtige Schnitt für ein Hundertstel des Stollen wäre. Dann zieht man vom Ende des Stollens los und macht zwischen dem ersten und dem zweiten Fähnchen einen Schnitt. Der, dessen Name auf dem ersten Fähnchen steht, bekommt dieses Stück.
Vom welchen Ende des Stollens sollen denn die Fähnchen gezählt werden? stänkert Holger. Da könnte jemand ja ein Riesenstück bekommen, über neun Meter.
Hör auf, Brüderchen! sagt Katja. Du weißt schon, was gemeint ist. Die müssen sich natürlich auf ein Stollenende geeinigt haben, wo sie ein Hunderstel abschneiden wollen. Und das ist dann auch das Ende, von dem das Fähnchenzählen beginnt.
Genau! fährt Sandra fort. Der mit dem ersten Fähnchen hat also sein Stück bekommen, und das ist größer als was er für ein Hundertstel des Stollens gehalten hatte. Für die 99 Anderen ist der Stollen ihrer jeweiligen Meinung nach um weniger als ein Hundertstel kleiner geworden, es sind also ihrer jeweiligen Meinung nach noch mehr als 99 Hundertstel des Stollens übrig, genug um für jeden der 99 ein Hundertstel des ursprünglichen Stollens zu liefern.
Also, der erste Schnitt war fair. fällt nun Gert ein. Keiner fühlt sich übervorteilt, und eine Person hat ein Hundertstel des Stollens bekommen, beziehungsweise, was sie für ein Hundertstel oder mehr hält. Und was jetzt mit den 99 Anderern passiert, ist auch klar.
Ja, sagt wieder Sandra. Das große Stollenstück, von dem jeder der 99 glaubt, dass es mehr als 99 Hundertstel des Riesenstollens ausmacht, muss jetzt fair in 99 Stücke geteilt werden.
Und wie soll das wieder gehen? fragt Katja ein bisschen abwesend.
Rekursiv, Katja, Rekursiv mit der gleichen Methode. Ist doch klar!
Wie? 'Rekursiv'? fragt Katja. Das Wort habe ich schon ein paarmal im Informatikunterricht gehört. Und da hat das für mich nie Sinn gemacht.
Schau, Katja! sagt Sandra. Wir wissen jetzt, wie man, wenn man 100 Personen und einen Stollen hat, vom Stollen ein Stück abschneiden kann, sodass eine Person mit ihrem Stück zufrieden ist und die 99 Anderen mit dem großen Stück, das sie gemeinsam haben, zufrieden sind. Sie müssen dieses große Stück fair in 99 Teile schneiden. Und das machen Sie nach der gleichen Methode: Jeder schätzt, wo er glaubt, dass man ein 99-stel des Stollens abschneiden würde, und steckt dort sein Fähnchen hinein. Dann wird wieder vom Ende gezählt und ein Schnitt zwischen dem ersten und zweiten Fähnchen gemacht. Das kurze Stück geht dann an den Besitzer des ersten Fähnchens, der damit mehr bekommt als er für ein 99-stel gehalten hatte. Für die übrigen 98 ging ihrer Meinung nach weniger als ein 99-stel verloren. Sie sind zufrieden, wenn das große Reststück fair in 98 Teile geteilt wird. Muss ich dir noch erklären, wie das geschieht, Katja?
Nein, danke, Sandra. Ich glaube ich habe es kapiert. sagt sie. Das funktioniert wieder nach der gleichen Methode mit 98 Fähnchen und einer bekommt ein 98-stel Stück, und die restlichen 97 müssen sich den Reststollen fair in 97 Stücke teilen. Das geht wieder mit 97 Fähnchen, und so weiter, und so weiter. Und das ist, was Rekursion bedeutet?
Richtig antwortet Sandra. Beziehungsweise auch richtig. In diesem Fall wollen wir einen Stollen fair in x Teile schneiden, also zum Beispiel in x=100 Teile, aber x=72315 wäre auch möglich, und wir tun das, indem wir es schaffen, dass einer seinen fairen Teil bekommt, und wir dazu noch das neue Problem bekommen, einen Stollen fair in x-1, also 99, Teile zu schneiden. Und das geht wieder mit dem gleichen Schema, und so fort.
Katja schaut ganz erstaunt. Ich glaube, mir ist ein Licht aufgegangen, Sandra. Das mit der Rekursion ist wirklich nicht so schwierig. Zumindest in diesem Fall hier.
Inzwischen hat jeder sein Stollenstück aufgegessen. Holger sagt etwas schlapp: Aber eines gefällt mir bei dieser Stollenaufteilmethode nicht. Wenn ich mir das so vorstelle, wie sie den 10 Meter langen Riesenstollen fair auf 100 Personen aufteilen wollen, dann braucht das irgendwie zu lange. Schon beim ersten Durchgang, bis sich da alle Hundert überlegt haben, wo sie ihr Fähnchen genau hinstecken wollen, das braucht schon einige Minuten. Und im nächsten Durchgang sind es noch immer 99 Personen.
Lass mich das einmal überschlagen! fällt ihm Gert ins Wort. Sagen wir, jeder braucht nur eine Sekunde, um sich den Platz für sein Fähnchen zu suchen und es in den Stollen zu stecken. Alles andere geht, sagen wir, blitzschnell und braucht keine Zeit. Beim ersten Durchgang müssen 100 Fähnchen gesteckt werden, braucht 100 Sekunden, beim zweiten Durchgang müssen 99 Fähnchen gesteckt werden, braucht 99 Sekunden, beim dritten Durchgang braucht man 98 Sekunden, und so fort. Insgesamt braucht man also 100+99+98+97+ . . . +3+2+1 Sekunden. Das sind 5050 Sekunden, also fast eineinhalb Stunden.
Woher weißt du das mit den 5050 so schnell? fragt Katja.
Ich habe halt aufgepasst und mir die Formel gemerkt: die Summe der Zahlen von 1 bis n ist n(n+1)/2. Da haben sie doch diese Story vom kleinen Klaus erzählt.
Du meinst den kleinen Gauss. fällt ihm Holger ein wenig verärgert ins Wort. Fürs faire Teilen in 100 Stücke braucht man also schon mindestens eineinhalb Stunden. Wieviel das wohl bei 1000 Stücken wäre?
Ungefähr 500000 Sekunden! erwidert Gert trotzig. Das ist, glaube ich, fast eine ganze Woche. Da verhungere ich ja, bevor ich mein Stollenstück bekomme.
Ja, oder der Stollen vergammelt. meint Holger. Das faire Teilen muss doch auch irgendwie schneller gehen.
Sie bleiben ruhig. Gert hat wieder begonnen, mit den Teppichfransen herumzuspielen.
Plötzlich sagt Sandra: Ich glaube, ich habe eine Idee, wie man schneller fair in viele Teile teilen könnte. Im Informatikunterricht haben wir etwas von 'Teile-und-Herrsche' gehört. Man müsste den Stollen irgendwie fair in zwei große Teile schneiden, ein Teil für die einen 50 Personen, den anderen Teil für die anderen 50. Die beiden Gruppen könnten dann gleichzeitig und unabhängig voneinander weitermachen.
Rekursiv. wirft Katja ein.
Ja, rekursiv, aber ein wenig anders als vorher.
Und wie soll das faire Teilen in zwei große Teile für jeweils 50 Personen genau funktionieren mit diesem 'Teile-und-Herrsche'? fragt Holger. Eigentlich sollte es hier wohl 'Teile-und-Esse' heißen.
Ich glaube, sagt Katja schnell, bei dir, Brüderchen, sollte es wohl eher 'Teile-nicht-und-Esse' heißen.
Bevor Holger etwas sagen kann, geht die Tür auf, und die Mutter kommt herein und fragt: Wo ist denn Tante Hedwigs Kuchen hin, den ich jetzt dem Herrn Maier hinüberbringen wollte?
Fragen
- Wenn man so einen Stollen fair in zwei Teile schneiden möchte, gibt es da außer der Nachbar-Maier-Methode noch eine andere?
- Bei der 'Teile-und-Herrsche'-Idee, die Sandra vorschlägt, muss bei, sagen wir, 100 Personen Folgendes passieren: Die Leute müssen in zwei Gruppen von je 50 geteilt werden, und der große Stollen muss in zwei Teile geschnitten werden, für jede Gruppe einen. Das soll so geschehen, dass jede der beiden Gruppen mit ihrem Stollenteil zufrieden ist. Wie kann man das erreichen?
- Könnte man bei der vorherigen Fragestellung auch so teilen, dass es eine Gruppe von 49 Personen gibt, und eine von 51, und beide Gruppen fühlten sich fair behandelt?
- Ist sogar jede beliebige Personenaufteilung fair behandelbar?
- Wenn Sandras 'Teile-und-Herrsche'-Idee rekursiv für 100 Personen durchgeführt würde, wie lange würde es brauchen, bis jede Person ihr Stollenstück bekommt? (Zähle dabei nur das Stecken von Fähnchen mit jeweils einer Sekunde.)
- Druckversion des Beitrags (pdf)
-
Ein englisch-sprachiges Buch über das faire Teilen:
Cake-Cutting Algorithms: Be Fair if You Can
by Jack Robertson and William Webb (1998). ISBN: 1-56881-076-8