Zadanie 3
2019
Etap II
★★★★☆Kombinatoryka
Logika
Turniej chłopców i dziewcząt
Powiązane zadania:
Zad. 5 (2019)
Treść zadania
W pewnym turnieju wzięli udział chłopcy i dziewczęta. Każda osoba rozegrała dokładnie jeden mecz z każdą inną osobą, nie było remisów. Po turnieju okazało się, że każdy przegrał co najmniej raz. Ponadto każdy chłopiec przegrał inną liczbę meczów niż każdy z pozostałych chłopców. Wykaż, że pewna dziewczynka wygrała mecz z pewnym chłopcem.
Umiejętności (7)
Wymagane umiejętności:
Grafy
Zasada szufladkowa
Dowód nie wprost
Techniki zliczania
Zdobywane umiejętności:
Grafy
Zasada ekstremalna
Dowód nie wprost
Wskazówki (0/4)
Wskazówka 1
Załóżmy nie wprost, że żadna dziewczynka nie wygrała z chłopcem. Oznacza to, że chłopcy ponosili porażki wyłącznie w meczach z innymi chłopcami.
Wskazówka 2
Niech oznacza liczbę chłopców. Skoro chłopcy przegrywali tylko między sobą, to z iloma maksymalnie przeciwnikami mógł przegrać dany chłopiec?
Wskazówka 3
Każdy chłopiec przegrał co najmniej raz. Wypisz zbiór wszystkich możliwych liczb porażek, jakie może mieć pojedynczy chłopiec w grupie osób.
Wskazówka 4
Mamy chłopców i każdy z nich ma inną liczbę porażek. Porównaj liczebność grupy chłopców z liczbą możliwych wartości porażek, które wyznaczyłeś.