Ich habe mir folgendes überlegt:
Nach Aufgabenstellung dürfen die guten Teams ja sozusagen vom "Grinch" eingeteilt werden (also von jemanden der will, dass wir verlieren). Also habe ich mich in die Rolle des Grinch begeben (hat Spaß gemacht)
Wenn man die 99 Spieler in folgende zwei Teilmengen aufteilt: A = { 1 ; 2 ; 3 ; ..... ; 50 } und B_1 = { 1 ; 51 ; 52 ; ..... ; 99 }
Dann gilt A geschnitten B ist die Menge {1}
Wenn man jetzt also immer nur einen gemeinsame Nummer hat kann man nicht zur zweiten Teilmenge rüber springen.
Jetzt bildet man noch folgende Teilmengen: B_2 = { 2 ; 51 ; 52 ; ..... ; 99 } bis B_50 = { 50 ; 51 ; 52 ; ..... ; 99 }
Dann kommen alle Paare 99 über 2 = 4851 vor. In Menge A sind dies: 50 über 2 = 1225
In jeder Menge B_1 sind dies weitere 1225
In der Menge B_2 sind weitere 49 neue Paare ==> Insgesamt 49*49= 2401 neue Paare
Insgesamt also 2*1225 + 2401 = 4851.
Jetzt können wir k = 48 wählen und trotzdem gelingt es nicht von der Menge A in die B_i zu springen und umgekehrt. Andererseits gibt es für jedes Paar in jeder Menge k = 48 Partner für ein "gutes" Team. Da man zwar zwischen den B_i hin und herspringen kann, aber niemals in die Menge A kommen kann, ohne nicht mindestens ein "schlechtes" Team einzusetzen, reicht k = 48 nicht.
Ab k = 49 müsste es also immer klappen, weil dann zwei gemeinsame Ziffern in einer der B_i und der Menge A vorkommen müssen.
Antwort 9 ist somit korrekt. (oder hat ein noch hinterhältiger Grinch, eine noch ungünstigere Zerlegung gefunden??)
Nach Aufgabenstellung dürfen die guten Teams ja sozusagen vom "Grinch" eingeteilt werden (also von jemanden der will, dass wir verlieren). Also habe ich mich in die Rolle des Grinch begeben (hat Spaß gemacht)
Wenn man die 99 Spieler in folgende zwei Teilmengen aufteilt: A = { 1 ; 2 ; 3 ; ..... ; 50 } und B_1 = { 1 ; 51 ; 52 ; ..... ; 99 }
Dann gilt A geschnitten B ist die Menge {1}
Wenn man jetzt also immer nur einen gemeinsame Nummer hat kann man nicht zur zweiten Teilmenge rüber springen.
Jetzt bildet man noch folgende Teilmengen: B_2 = { 2 ; 51 ; 52 ; ..... ; 99 } bis B_50 = { 50 ; 51 ; 52 ; ..... ; 99 }
Dann kommen alle Paare 99 über 2 = 4851 vor. In Menge A sind dies: 50 über 2 = 1225
In jeder Menge B_1 sind dies weitere 1225
In der Menge B_2 sind weitere 49 neue Paare ==> Insgesamt 49*49= 2401 neue Paare
Insgesamt also 2*1225 + 2401 = 4851.
Jetzt können wir k = 48 wählen und trotzdem gelingt es nicht von der Menge A in die B_i zu springen und umgekehrt. Andererseits gibt es für jedes Paar in jeder Menge k = 48 Partner für ein "gutes" Team. Da man zwar zwischen den B_i hin und herspringen kann, aber niemals in die Menge A kommen kann, ohne nicht mindestens ein "schlechtes" Team einzusetzen, reicht k = 48 nicht.
Ab k = 49 müsste es also immer klappen, weil dann zwei gemeinsame Ziffern in einer der B_i und der Menge A vorkommen müssen.
Antwort 9 ist somit korrekt. (oder hat ein noch hinterhältiger Grinch, eine noch ungünstigere Zerlegung gefunden??)