- Narzędzia
- Obiekty
- Słowa kluczowe
- Kategoria
- Kombinatoryka
Zadanie ZM-1596
o zadaniu...
- Publikacja w Delcie: marzec 2019
- Publikacja elektroniczna: 1 marca 2019
Definicje
Przez n-turniej będziemy rozumieli układ rozgrywek, w którym każda para spośród zawodników rozegrała dokładnie jeden mecz i nie było remisów.
owiemy, że zawodnik jest mistrzem, jeśli dla każdego zawodnika z którym przegrał, istnieje zawodnik który przegrał z i wygrał z Innymi słowy, mistrz to zawodnik, który wygrał z każdym innym bezpośrednio lub pośrednio.
Wyznaczyć wszystkie dla których istnieje -turniej, w którym każdy jest mistrzem.
Rozwiązanie
Odpowiedź.
Nazwijmy mistrzowskim taki -turniej, w którym każdy jest mistrzem. Udowodnimy, że jeśli istnieje mistrzowski -turniej, to istnieje mistrzowski -turniej.
Niech będą zawodnikami pewnego mistrzowskiego -turnieju, a i takimi dwoma dodatkowymi zawodnikami, że wygrał z a ponadto wygrał z i przegrał z dla każdego Wówczas -turniej powstały przez dołączenie zawodników i jest mistrzowski.
Nietrudno sprawdzić, że -turniej złożony z zawodników takich, że wygrał z wygrał z wygrał z oraz -turniej pokazany na poniższym rysunku (punkty oznaczają zawodników, a strzałka z do że wygrał z ) są mistrzowskie. W połączeniu z konkluzją poprzednich dwóch akapitów prowadzi to do wniosku, że -turniej mistrzowski istnieje dla każdej liczby nieparzystej oraz dla każdej liczby parzystej
Pozostaje udowodnić, że nie istnieje mistrzowski 4-turniej. Przypuśćmy, że jednak istnieje, i oznaczmy zawodników przez w taki sposób, że wygrał z wygrał z oraz (bez straty ogólności) wygrał z Wówczas, skoro jest mistrzem, to musiał pośrednio wygrać z - jedyna możliwość jest taka, że wygrał z a wygrał z Jednak wówczas ten z zawodników który przegrał mecz między nimi, nie miał jak wygrać pośrednio z tym drugim - sprzeczność.