Zadanie 3

2010
Etap II
★★★★
Kombinatoryka
Logika
Turniej tenisa stołowego
Treść zadania
W turnieju tenisa stołowego wzięło udział nn zawodników (n4n \geq 4). 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 AA, BB i CC, że AA wygrał z BB, BB wygrał z CC oraz CC wygrał z AA.
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 Z1,Z2,,ZnZ_1, Z_2, \ldots, Z_n. Co wiemy o wyniku meczu między ZiZ_i a Zi+1Z_{i+1} (oraz między ZnZ_n a Z1Z_1)?
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. Z1,Z2,Z3Z_1, Z_2, Z_3. Jakie wyniki meczów między nimi już znamy?
Wskazówka 3
Znamy wyniki meczów Z1Z_1 z Z2Z_2 i Z2Z_2 z Z3Z_3. Rozważ dwa możliwe wyniki meczu między Z1Z_1 a Z3Z_3. 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 Z1Z_1 pokonał Z3Z_3. Co ten wynik, w połączeniu z brakiem cyklu z udziałem Z1,Z3,Z4Z_1, Z_3, Z_4, mówi nam o wyniku meczu Z1Z_1 z Z4Z_4? Spróbuj uogólnić tę obserwację.
Prześlij rozwiązanie

Zaloguj się, aby przesłać swoje rozwiązanie

Zaloguj się