Zadanie 3
2010
Etap II
★★★★☆Kombinatoryka
Logika
Turniej tenisa stołowego
Treść zadania
W turnieju tenisa stołowego wzięło udział zawodników (). Każdy zawodnik rozegrał dokładnie jeden mecz z każdym innym zawodnikiem, żaden mecz nie zakończył się remisem. Po turnieju wszyscy zawodnicy usiedli przy okrągłym stole w taki sposób, że każdy zawodnik wygrał z osobą siedzącą obok niego z jego lewej strony. Wykaż, że istnieją tacy trzej zawodnicy , i , że wygrał z , wygrał z oraz wygrał z .
Umiejętności (4)
Wymagane umiejętności:
Grafy
Analiza przypadków
Zdobywane umiejętności:
Grafy
Analiza przypadków
Wskazówki (0/4)
Wskazówka 1
Oznaczmy zawodników siedzących przy stole zgodnie z ruchem wskazówek zegara jako . Co wiemy o wyniku meczu między a (oraz między a )?
Wskazówka 2
Poszukajmy cyklu złożonego z trzech zawodników. Dobrym punktem wyjścia jest przyjrzenie się trzem kolejnym zawodnikom przy stole, np. . Jakie wyniki meczów między nimi już znamy?
Wskazówka 3
Znamy wyniki meczów z i z . Rozważ dwa możliwe wyniki meczu między a . Czy w którymś z tych przypadków od razu znajdujemy szukany cykl?
Wskazówka 4
Jeśli nie znalazłeś cyklu, to znaczy, że pokonał . Co ten wynik, w połączeniu z brakiem cyklu z udziałem , mówi nam o wyniku meczu z ? Spróbuj uogólnić tę obserwację.