Beim alljährlichen großen Pferderennen in der antiken Stadt Qarth, so sagt man, treten die 25 schnellsten Pferde der Welt an. Da sich keiner der Pferdebesitzer in die Karten schauen lassen möchte, ist im Voraus nicht bekannt, welches Pferd wie schnell ist.
Von Zeitmessgeräten halten die Qarther nicht viel. Stattdessen bevorzugt es das Publikum, wenn die Rangfolge über direkte Duelle bestimmt wird.
Allerdings verfügt die Qarther Pferderennbahn nur über 5 Spuren.
Wie viele Rennen müssen mindestens durchgeführt werden, um die drei schnellsten der 25 Pferde zu küren und das Podest korrekt zu besetzen?
(Die Pferde sind in jedem ihrer Rennen gleich schnell. Außerdem gehen wir davon aus, dass es keine gleich schnellen Pferde gibt.)
Lösung
Es müssen mindestens 7 Pferderennen mit jeweils 5 Teilnehmern durchgeführt werden, um die ersten drei Plätze korrekt zu besetzen.
Dazu unterteilen wir diese 7 Pferderennen in drei Typen: 5 Vorläufe 1 Finale 1 „Best of the Rest“-Rennen
Die Vorläufe: Rennen 1-5
Die ersten fünf Rennen sind die sogenannten Vorläufe. Dabei treten die 25 Pferde in ausgelosten Fünfergruppen gegeneinander an. Die Reihenfolge der Pferde in jedem Vorlauf wird notiert. Der erste Platz eines Vorlaufes ist ganz rechts (rot markiert), der zweite Platz dahinter usw.
Die jeweiligen Sieger der fünf Vorläufe (alle Pferde ganz rechts in rot) qualifizieren sich für das Finale. Unter ihnen muss sich auch das insgesamt schnellste Pferd befinden.
Das Finale: Rennen 6
Im Finale treten die fünf Vorlaufsieger gegeneinander an und werden ihrer Platzierung entsprechend von rechts nach links geordnet.
Das schnellste dieser Pferde (ganz rechts rechts mit dem goldenen Lorbeerkranz) ist garantiert auch das schnellste aller 25 Pferde. Es ist nämlich schneller als alle anderen Vorlaufsieger, welche wiederum schneller waren als alle anderen Teilnehmer ihrer Vorläufe.
Platz 1 ist also bereits vergeben.
Best of the Rest: Rennen 7
Es fehlen die Plätze 2 und 3. Die bisherigen Rennen reichen nicht aus, um diese festzulegen.
Für die folgenden Überlegungen, werden die Vorläufe nun nach dem Abschneiden ihres jeweiligen Vorlaufsiegers im Finale geordnet. Der Vorlauf mit dem schnellsten Finalpferd ist ganz oben, der Vorlauf mit dem langsamsten Finalpferd ganz unten.
Ohne Beschränkung der Allgemeinheit entspreche die Zahl des Vorlaufes auch der Platzierung seines Siegerpferdes im Finale. (Jede andere Reihenfolge ändert nichts an der Argumentation, man müsste allerdings trotzdem irgendeine Reihenfolge festlegen.)
Für den Hinterkopf: Um die noch bestmögliche Platzierung eines Pferdes zu bestimmen, zählt man in der Tabelle die Schritte bis zum zugehörigen Vorlaufsieger nach rechts und von dort zum Gesamtsieger nach oben. Denn jedes Pferd ist sicher langsamer als alle Pferde rechts von ihm und sicher langsamer als alle Pferde über seinem Vorlaufsieger. So könnte man direkt alle Pferde suchen, die noch Platz 3 erreichen können.
Um das Podest fertig zu besetzen, überlegen wir uns, welche Pferde auf keinen Fall zu den drei schnellsten gehören können. Wir suchen also diejenigen Pferde, von denen wir sicher wissen, dass sie langsamer sind als mindestens drei andere Pferde.
Damit scheiden als erstes alle Pferde aus, die in ihrem jeweiligen Vorlauf nur 4. oder 5. geworden sind. Wenn ein Pferd nicht einmal in seinem eigenen Vorlauf unter den Top 3 ist, kann es auch nicht zu den Top 3 aller 25 Pferde gehören.
Außerdem scheiden die beiden langsamsten Pferde aus dem Finale aus (Sieger aus dem 4. und 5. Vorlauf), denn auch hier gibt es ja mindestens drei schnellere Pferde. Damit scheiden aber automatisch auch alle anderen Pferde aus den Vorläufen 4 und 5 aus, da diese ja noch langsamer sind.
Lassen wir das Siegerpferd außen vor, haben wir mit 8 übrigen Podestkandidaten immer noch zu viele Teilnehmer für ein einziges Rennen. Wir können aber noch weitere Pferde ausschließen.
Dazu benennen wir die Pferde nach dem Schema („Nummer des Vorlaufs“ | „Platzierung im Vorlauf“). Das Siegerpferd heißt also (1|1.).
In Vorlauf 3 kommt nur der dortige Sieger, genannt (3|1.), überhaupt noch für Bronze in Frage. So scheidet (3|2.) beispielsweise aus, weil (3|1.), (2|1.) und (1|1.) sicher schneller sind. Natürlich scheidet dann auch das noch langsamere Pferd (3|3.) aus.
Aus Vorlauf 2 scheidet (2|3.) für das Podest aus, weil (2|2.), (2|1.) und (1|1.) schneller sind.
Damit bleiben also noch fünf Pferde übrig, die die verbliebenen beiden Podestplätze im „Best of the Rest“-Rennen unter sich ausmachen.
Bonusfragen: Welche Pferde können noch 2. werden? Wie viele und welche Podestkonstellationen sind möglich? . . . . . . . . . . . . . . . .
Lösungen zu den Bonusfragen:
Welche Pferde können noch 2. werden? Tatsächlich können nur noch zwei Pferde den 2. Platz belegen. Mit der obigen Notation sind das die Pferde (1|2.) und (2|1.). Alle übrigen Pferde sind langsamer als mindestens eines dieser beiden Pferde und natürlich sowieso langsamer als das schnellste Pferd überhaupt, (1|1.)
Wie viele und welche Podestkonstellationen sind möglich? Es sind drei verschiedene Podestkonstellationen möglich.
Konstellation 1: 1. Platz: (1|1.) 2. Platz: (1|2.) 3. Platz: (1|3.) Hier waren also die drei schnellsten Pferde allesamt im selben Vorlauf.
Konstellation 1: 1. Platz: (1|1.) 2. Platz: (2|1.) 3. Platz: (2|2.) Auf dem Podest landen zwei Pferde aus Vorlauf 2.
Konstellation 1: 1. Platz: (1|1.) 2. Platz: (2|1.) 3. Platz: (3|1.) In diesem Fall haben alle Pferde auf dem Podest ihren Vorlauf gewonnen.
Schreibe einen Kommentar