- 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ść.