W turnieju tenisa stołowego uczestniczyło \(\displaystyle{ 2n}\) zawodników. Każdy zawodnik rozegrał z każdym innym zawodnikiem co najwyżej jeden mecz. Po turnieju okazało się, że dokładnie \(\displaystyle{ n}\) zawodników rozegrało po dwa mecze, a pozostałych \(\displaystyle{ n}\) zawodników po trzy mecze. Wyznacz wszystkie liczby całkowite dodatnie \(\displaystyle{ n}\), dla których taka sytuacja jest możliwa.
Jak to zrobić?
W turnieju tenisa stołowego
-
MrCommando
- Użytkownik
- Posty: 554
- Rejestracja: 5 gru 2016, o 21:55
- Płeć: Mężczyzna
- Lokalizacja: Płock/MiNI PW
- Podziękował: 48 razy
- Pomógł: 107 razy
W turnieju tenisa stołowego
Problem można przetłumaczyć na język teorii grafów. Chcemy znaleźć takie \(\displaystyle{ n}\), żeby istniał graf o \(\displaystyle{ 2n}\) wierzchołkach, taki że połowa jego wierzchołków jest stopnia dwa, a druga stopnia trzy. Jak zsumujemy stopnie w grafie spełniającym takie warunki to dostaniemy \(\displaystyle{ 5n}\). Z lematu o uściskach dłoni wynika, że taka suma jest liczbą parzystą, co implikuje że \(\displaystyle{ n}\) musi być liczbą parzystą.
Istotnie dla parzystych \(\displaystyle{ n}\) można skonstruować taki graf. Na przykład dla \(\displaystyle{ n=2}\) rozważ graf \(\displaystyle{ G=(V,E)}\) taki, że \(\displaystyle{ V=\{1,2,3,4\}}\) i \(\displaystyle{ E=\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{3,4\}\}}\). Dla większych \(\displaystyle{ n}\) konstrukcja analogiczna.
Istotnie dla parzystych \(\displaystyle{ n}\) można skonstruować taki graf. Na przykład dla \(\displaystyle{ n=2}\) rozważ graf \(\displaystyle{ G=(V,E)}\) taki, że \(\displaystyle{ V=\{1,2,3,4\}}\) i \(\displaystyle{ E=\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{3,4\}\}}\). Dla większych \(\displaystyle{ n}\) konstrukcja analogiczna.