optimale Strategie < Känguru < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 15:38 Fr 23.10.2020 | | Autor: | ms2008de |
| Aufgabe | Im Informatikraum haben wir 25 Rennroboter, die alle verschieden schnell sind. Wir sollen die drei schnellsten ermitteln. Auf einer Teststrecke treten jeweils fünf Roboter gegeneinander an. Vor jedem Rennen darf festgelegt werden, welche fünf Roboter fahren sollen. Nach jedem Rennen wird nur die
Reihenfolge des Zieleinlaufs bekannt gegeben. Wir haben uns eine Strategie überlegt, wie wir die drei schnellsten Roboter mit N Rennen bestimmen können, egal wie diese Rennen ausgehen. Was ist das kleinstmögliche N? |
Hallo,
die Aufgabe entstammt dem diesjährigen Känguru-Wettbewerb für die Klassenstufen 11-13, Aufgabe C9. Laut Lösung sollte man innerhalb von 7 Rennen die schnellsten 3 Roboter bestimmen können.
Zunächst war meine Überlegung, dass man den schnellsten Roboter innerhalb von 6 Rennen bestimmen kann, indem man alle 25 in je 5 Rennen gegeneinander fahren lässt und dann abschließend die 5 jeweiligen Sieger gegeneinander fahren lässt. Doch wie ermittelt man optimalerweise mit wenig Rennen den zweit- und drittschnellsten Roboter?
Generell dachte ich mir, kann man die 3 schnellsten Roboter bestimmen, indem man zunächst zufällig 5 Roboter gegeneinander fahren lässt und dann die beiden Letztplatzierten immer wieder austauscht gegen Roboter, die noch nicht gefahren sind, doch dann bräuchte man schon 11 Rennen für die Bestimmung der 3 schnellsten. Wo kann man hier also weiter optimieren...?
Vielen Dank schon mal für jede Hilfe im Voraus.
Viele Grüße
ms2008de
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:01 Fr 23.10.2020 | | Autor: | statler |
Hi!
Ich komme mal mit einer ersten Verbesserung. Im 6. Rennen lassen wir die 5 Zweitplazierten gegeneinander fahren. Dann kann ich weitere 8 Kandidaten aussortieren, bleiben 7. Dann lasse ich im 7. Rennen den besten Zweiten gegen die anderen Sieger der Rennen 1 bis 5 fahren. Danach kann ich mindestens 2 weitere Teilnehmer eliminieren, bleiben 5. Und im 8. Rennen kann ich alles klären.
Also Zwischenstand: 5 Rennen brauche ich mindestens, und 8 reichen.
Meine Vermutung ist, daß man die ersten 5 Rennen schon anders organisieren muß.
Gruß Dieter
PS: Will man auch die Rangfolge der 3 Schnellsten ermitteln, oder reicht, wer dazugehört, oder ist das für die Strategie egal?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:17 Fr 23.10.2020 | | Autor: | tobit09 |
Hallo zusammen,
hier eine mögliche Strategie, die mit 7 Rennen auskommt (und auch die Rangfolge der drei schnellsten Roboter mitzubestimmen vermag):
Wir lassen in den ersten fünf Runden jeden der 25 Roboter genau einmal antreten.
In der sechsten Runde lassen wir die fünf in den ersten fünf Runden erstplatzierten Roboter gegeneinander antreten.
Damit kennen wir den schnellsten Roboter.
Man kann sich weiter überlegen, dass zu diesem Zeitpunkt nur noch fünf Roboter für die Plätze zwei und drei in der Gesamtrangfolge in Frage kommen.
Diese fünf Roboter lässt man in der siebten Runde einfach gegeneinander antreten.
Den vermutlich schwierigeren Part habe ich aber noch nicht lösen können: Wie lässt sich beweisen, dass sechs Runden nicht ausreichen?
Wobei auch mir unklar ist, ob die Rangfolge innerhalb der schnellsten drei mitzubestimmen ist oder nicht.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:31 Fr 23.10.2020 | | Autor: | ms2008de |
Danke schonmal für die beiden Antworten.
Klar ist, wenn 7 tatsächlich die Lösung ist, so bestimmst du automatisch mit der von dir beschriebenen Strategie ja auch exakt wer am Ende der Zweit- und Drittschnellste Roboter ist, von daher scheint das ja keine Rolle zu spielen.
Klar ist außerdem, um sich der Reihenfolge absolut sicher sein zu können, muss jeder Roboter mindestens einmal gefahren sein, was allein schon mindestens 5 Rennen sind.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:30 Fr 23.10.2020 | | Autor: | Fulla |
Hallo Tobias,
und was ist, wenn in einer der fünf ersten Gruppen alle der drei schnellsten Roboter sind?
Wenn nur die besten aus den ersten fünf Runden erneut antreten, "verlierst" ja so den Zweit- und Drittschnellsten.
Meiner Meinung nach ist die Rangfolge hier gar nicht gefragt. Die Aufgabenstellung lautet im Original ebenso "Wir sollen die drei schnellsten ermitteln."
Ich habe aber ehrlich gesagt auch (noch) keine Lösung für nur sieben Runden gefunden. Ich bezweifle sogar, dass man oben genanntes Szenario mit sieben Runden behandelt bekommt...
Lieben Gruß
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:35 Sa 24.10.2020 | | Autor: | ms2008de |
Hallo Fulla,
die Lösung von Tobias führt in nur 7 Runden dazu, dass wir die Reihenfolge unter den schnellsten 3 auch bestimmen können.
> und was ist, wenn in einer der fünf ersten Gruppen alle
> der drei schnellsten Roboter sind?
> Wenn nur die besten aus den ersten fünf Runden erneut
> antreten, "verlierst" ja so den Zweit- und
> Drittschnellsten.
Also nochmal: in Runde 1 fährt in 5 Rennen jeder der 25 Roboter genau einmal. In Rennen 6 fahren die Sieger der ersten 5 Rennen gegeneinander und der Sieger von Rennen 6 ist der schnellste Roboter. In Rennen 7 fahren: Der Zweit- und Drittplatzierte der ersten Runde, bei dem der schnellste Roboter teilgenommen hat, gegen den Zweitplatzierten aus Rennen 6 und den Zweitplatzierten aus der ersten Runde, bei dem der Zweitplatzierte aus Rennen 6 teilgenommen hat, und als 5. Starter tritt dann schließlich noch der Drittplatzierte Roboter aus Rennen 6 an.
Die ersten beiden Roboter in Rennen 7 sind dann die Zweit- und Drittschnellsten Roboter insgesamt.
Viele Grüße
ms2008de
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:18 Sa 24.10.2020 | | Autor: | Fulla |
Hallo ms2008de,
ich habe es mir mal aufgeschrieben/gezeichnet und meinen Denkfehler erkannt, man kann nämlich bei jedem Rennen mehr Roboter ausschließen, als ich dachte.
Wenn man die Roboter von 1 bis 25 durchnummeriert sieht das etwa so aus (Rangfolge jeweils von links nach rechts, Sieger fett markiert):
R1: 1, 2, 3, 4, 5
R2: 6, 7, 8, 9, 10
R3: 11, 12, 13, 14, 15
R4: 16, 17, 18, 19, 20
R5: 21, 22, 23, 24, 25
R6: 1, 6, 11, 16, 21
Jetzt kann man aussortieren, welche Roboter garantiert nicht in den Top-Drei sein können:
R1: 1, 2, 3, 4, 5
R2: 6, 7, 8, 9, 10
R3: 11, 12, 13, 14, 15
R4: 16, 17, 18, 19, 20
R5: 21, 22, 23, 24, 25
R6: 1, 6, 11, 16, 21
Wir wissen schon, dass Roboter 1 der schnellste ist und veranstalten nun
R7: 2, 3, 6, 7, 11
und erhalten so den zweit- und drittschnellsten (mit Rangfolge).
Vielleicht hilft diese Lösung ja dem ein oder anderen...
Lieben Gruß
Fulla
|
|
|
|
