Zadanie 2
2008
Etap III
★★★★☆Kombinatoryka
Teoria liczb
Turniej tenisa stołowego
Treść zadania
W turnieju tenisa stołowego uczestniczyło zawodników. Każdy zawodnik rozegrał z każdym innym zawodnikiem co najwyżej jeden mecz. Po turnieju okazało się, że dokładnie zawodników rozegrało po dwa mecze, a pozostałych zawodników po trzy mecze. Wyznacz wszystkie liczby całkowite dodatnie , dla których taka sytuacja jest możliwa.
Umiejętności (5)
Wymagane umiejętności:
Grafy
Podwójne zliczanie
Konstrukcja przykładu
Zdobywane umiejętności:
Grafy
Podwójne zliczanie
Wskazówki (0/4)
Wskazówka 1
Przedstaw zawodników jako wierzchołki grafu, a rozegrane mecze jako jego krawędzie. Jaki jest stopień każdego wierzchołka, czyli ile krawędzi z niego wychodzi?
Wskazówka 2
Oblicz sumę stopni wszystkich wierzchołków w tym grafie. Tę samą wielkość można wyrazić w zależności od całkowitej liczby rozegranych meczy. Co wynika z porównania tych dwóch wyrażeń?
Wskazówka 3
Zależność, którą znajdziesz, narzuca pewien warunek na liczbę . Gdy już go poznasz, pozostaje sprawdzić, czy dla każdej liczby spełniającej ten warunek da się skonstruować odpowiedni turniej.
Wskazówka 4
Aby pokazać, że dla danej wartości turniej jest możliwy, spróbuj go skonstruować. Ustaw zawodników w okręgu i niech każdy zagra z sąsiadami. Jakie stopnie mają teraz wierzchołki i jak je zmodyfikować, dodając kilka meczy?