Weihnachtsmann rot

Aufgabe vom 20. Dezember

Gemischtes Doppel

Autor: Rudi Pendavingh

Aufgabe:

Die vier Wichtelfrauen Alix, Bona, Clio, Dana und die vier Wichtelmänner Emil, Fred, Gerd, Hans nehmen an einem Tennisturnier für gemischte Doppel teil. Jeder der acht Wichtel hat strikte Vorlieben für die vier möglichen Tennispartner. Zum Beispiel möchte Alix am liebsten mit Fred zusammen spielen, am zweitliebsten mit Hans, am drittliebsten mit Emil, und am viertliebsten mit Gerd. Die Vorlieben der Wichtel sind in der folgenden Tabelle zusammengefasst:





Alix:Fred, Hans, Emil, Gerd Emil:Alix, Clio, Bona, Dana
    
Bona: Gerd, Emil, Fred, Hans Fred: Bona, Dana, Clio, Alix
    
Clio: Hans, Fred, Gerd, Emil Gerd:Clio, Alix, Dana, Bona
    
Dana: Emil, Gerd, Hans, Fred Hans:Dana, Bona, Alix, Clio




Die Wichtel losen zunächst einmal eine zufällige Anfangspaarung P1 aus:

P1:    Alix–Gerd   Bona –Hans    Clio–Emil   Dana –Fred

In dieser Paarung P1 bilden Alix und Emil ein unzufriedenes Paar: Alix spielt lieber mit Emil als mit ihrem momentanen Partner Gerd zusammen, und Emil spielt lieber mit Alix als mit seiner momentanen Partnerin Clio zusammen. Alix und Emil beschließen daher, ein Paar zu bilden. Die im Stich gelassenen Partner Clio und Gerd bilden ebenfalls ein neues Paar:

P2:    Alix–Emil   Bona –Hans   Clio–Gerd    Dana –Fred

Wir sagen, dass die Paarung P1 durch das unzufriedene Paar Alix und Emil in die Paarung P2 übergeht. In der neuen Paarung P2 formen Bona und Fred ein unzufriedenes Paar: Bona spielt lieber mit Fred als mit ihrem momentanen Partner Hans zusammen, und Fred spielt lieber mit Bona als mit seiner momentanen Partnerin Dana zusammen. Die Paarung P2 geht nun in die folgende Paarung P3 über:

P3:    Alix–Emil   Bona –Fred   Clio–Gerd   Dana –Hans

Da es in P3 keine unzufriedene Paare gibt, terminiert der Prozess. Wir haben also eine Kette P 1 , P 2 , P 3 mit drei Paarungen gefunden, die durch unzufriedene Paare ineinander übergehen.

In dieser Aufgabe betrachten wir derartige Ketten von Paarungen. Eine Kette beginnt mit einer beliebigen Paarung P1 und geht dann Schritt für Schritt in weitere Paarungen P2,P3,P4, über. Eine Paarung Pi kann dabei in eine neue Paarung P i+1 übergehen, falls es in Pi eine Wichtelfrau F und einen Wichtelmann M mit folgenden Eigenschaften gibt: Die Frau F spielt lieber mit M zusammen als mit ihrem momentanen Partner M, und der Mann M spielt lieber mit F zusammen als mit seiner momentanen Partnerin F. Wir sagen dann, dass F und M ein unzufriedenes Paar (F,M) bilden. Die beiden Paare (F,M) und (F,M) in der Paarung Pi werden dann durch die beiden Paare (F,M) und (F,M) ersetzt und das ergibt die Nachfolgepaarung P i+1 . (Es ist möglich, dass eine Paarung Pi zwei oder mehr verschiedene potentielle Nachfolgepaarungen hat. Falls Pi nämlich zwei oder mehr verschiedene unzufriedene Paare enthält, so könnte jedes dieser unzufriedenen Paare zu einer anderen Nachfolgepaarung führen.)

Wir wollen von Euch wissen, wie lang solche Ketten überhaupt werden können. Mit L bezeichnen wir die Länge der längstmöglichen derartigen Kette und mit K bezeichnen wir die Länge der längstmöglichen Kette, in der jede Paarung höchstens einmal vorkommt.

Die Aufgabe als PDF runterladen (flagge nl NL Download)

Antwortmöglichkeiten:
(Lösung als PDF herunterladen)

  1.   K = 8  und  L = 8

  2.   K = 9  und  L = 9

  3.   K = 10  und  L = 10

  4.   K = 11  und  L = 11

  5.   K = 12  und  L = 12

  6.   K = 13  und  L unendlich

  7.   K = 14  und  L unendlich

  8.   K = 15  und  L unendlich

  9.   K = 16  und  L unendlich

  10.   K = 17  und  L unendlich

Sie müssen sich einloggen um die Aufgaben abgeben zu können.