© Friederike Hofmann, MATH+
Autor: Tobias Paul (HU Berlin)
Projekt: EF 4-7
Aufgabe
Um die kreative Freiheit bei den Geschenken zu beflügeln, hat der Weihnachtsmann ein neues System eingeführt: Jedes Geschenk besteht aus Einzelteilen und soll frei von den Weihnachtselfen zusammengesetzt werden. Dazu bekommt zu Beginn jeder Elf ein Einzelteil des großen Geschenks. Um die Teile geeignet miteinander zu verbinden, wuseln die Elfen wild durcheinander. Bei n anwesenden Elfen dauert es 1/(n(n-1)) Tage, bis sich zwei Elfen mit passenden Teilen finden. Wenn sich zwei Elfen gefunden haben, setzen sie ihre Teile sofort zusammen. Unmittelbar danach holt sich einer der beiden Elfen seinen Arbeitslohn beim Weihnachtsmann ab und verschwindet anschließend in den wohlverdienten Feierabend. Der andere Elf behält nun das größere Teil bei sich und sucht in dem Gewusel weiter nach passenden Stücken. Danach bleiben n-1 Elfen übrig, und sie wiederholen das analoge Verfahren, bei dem es 1/((n- 1)(n- 2)) Tage dauert, bis zwei passende Elfen einander finden. So geht das Prozedere weiter, bis schließlich die letzten zwei (mittlerweile sehr großen) Teile zum fertigen Geschenk werden und die letzten zwei Elfen gehen dürfen.
Der Weihnachtsmann muss natürlich sicherstellen, dass die Geschenke auch rechtzeitig fertig werden. Außerdem muss er für die Kasse natürlich wissen, wie hoch seine Lohnkosten pro Geschenk maximal sind. Dabei ist nach Tarifvertrag eine Vergütung in Höhe von einem Keks am Tag für jeden Elfen vereinbart, wobei der Betrag auf den Krümel exakt ausgezahlt wird. Da die Anforderungen an die Geschenke weiter wachsen und immer mehr einzelne Teile erfordern, möchte er einen universellen Rahmen für das Geschenke-Zusammenstellen schaffen. Er möchte also Zahlen t und k finden, sodass
- (a) jedes Geschenk, unabhängig von der Anzahl der Teile, in t Tagen zusammengebaut werden kann
- (b) jedes Geschenk, unabhängig von der Anzahl der Teile, höchstens k Kekse kostet.
Derzeit ist sich der Weihnachtsmann nicht sicher, ob solche Werte t und k existieren, aber wenn sie es tun, möchte er, dass sie so klein wie möglich sind. Kannst du dem Weihnachtsmann helfen, die Antwort zu finden, also die minimalen Werte von t und k (falls sie existieren)?
Antwortmöglichkeiten:
- t=0.5 und k=1
- t=0.5 und k=2
- t=0.5 und k kann nicht gefunden werden
- t=1 und k=1
- t=1 und k=2
- t=1 und k kann nicht gefunden werden
- t=2 und k=1
- t=2 und k=2
- t=2 und k kann nicht gefunden werden
- beides t und k können nicht gefunden werden.
Projektbezug:
Der beschriebene Prozess ist ein sogenannter Koaleszenz-Prozess. Dabei verschmelzen immer zwei Partikel zu einem größeren. In diesem Beispiel handelt es sich um den Kingman-Koaleszenten mit leicht angepasster Verschmelzungsrate. Der Koaleszent beschreibt dabei in der Biologie die Genealogie einer Teilpopulation. Die Zeit bis zum letzten verschmelzen ist dann die Zeit bis zum jüngsten gemeinsamen Vorfahren. In Aufgabenteil (a) sehen wir somit, wie lange es dauert, bis der jüngste gemeinsame Vorfahre für eine beliebig große Teilpopulation erreicht wurde. Teil (b) beschäftigt sich dann mit der Gesamtsumme der sogenannten Astlängen.