Zadanie 5
2019
Etap I
★★★☆☆Kombinatoryka
Logika
Turniej 8 zawodników z remisami
Treść zadania
W turnieju wzięło udział 8 zawodników. Każda para zawodników rozegrała dokładnie jeden mecz, który zakończył się zwycięstwem jednego z nich lub remisem. Zwycięzca meczu otrzymywał 2 punkty, jego przeciwnik 0 punktów, a w przypadku remisu obaj zawodnicy uzyskiwali po 1 punkcie. Po rozegraniu wszystkich meczów okazało się, że każdy zawodnik miał tę samą liczbę punktów. Jaka jest najmniejsza możliwa liczba meczów, które zakończyły się remisem? Odpowiedź uzasadnij.
Umiejętności (6)
Wymagane umiejętności:
Grafy
Parzystość i nieparzystość
Techniki zliczania
Zdobywane umiejętności:
Grafy
Zasada ekstremalna
Konstrukcja przykładu
Wskazówki (0/4)
Wskazówka 1
Oblicz, ile jest wszystkich meczów w turnieju i jaka jest całkowita pula punktów do zdobycia. Ile punktów musi mieć każdy zawodnik?
Wskazówka 2
Każdy zawodnik musi zdobyć nieparzystą liczbę punktów. Zastanów się, jakie kombinacje zwycięstw (2 pkt) i remisów (1 pkt) dają taki wynik.
Wskazówka 3
Zwróć uwagę, że każdy zawodnik musi mieć nieparzystą liczbę remisów. Policz, ile łącznie "końców remisowych" muszą mieć wszyscy zawodnicy razem.
Wskazówka 4
Każdy remis angażuje dwóch zawodników (daje dwa "końce remisowe"). Użyj tego, aby znaleźć dolne ograniczenie na liczbę remisów, a następnie skonstruuj przykładowy turniej.