Okrągły stół i trójkąty

Delta, grudzień 2016

o artykule ...

Publikacja w Delcie: grudzień 2016
Publikacja elektroniczna: 30 listopada 2016
Wersja do druku [application/pdf]: (62 KB)

Turniej to zestaw rozgrywek pomiędzy pewną liczbą graczy, w którym każdy gra dokładnie jeden mecz z każdym z pozostałych i nie ma remisów. Jeśli zawodnik wygrał wszystkie swoje mecze, nazwiemy go zwycięzcą.

Cykl to taki ciąg co najmniej trzech różnych zawodników, w którym każdy wygrał z następnym, a ostatni z pierwszym. Trójkąt to cykl o długości trzy.

Oznaczenia: $A$ oznacza, że $A$ wygrał z $B. |$

Na Rys. 1 uczestnicy cyklu przy okrągłym stole; każdy wygrał z osobą siedzącą na lewo od niego.

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Okrągły stół i trójkąty»Zadanie 1

o zadaniu...

Zadanie pochodzi z artykułu Okrągły stół i trójkąty
Publikacja w Delcie: grudzień 2016
Publikacja elektroniczna: 30 listopada 2016
Artykuł źródłowy w wersji do druku [application/pdf]: (62 KB)

Wykaż, że w każdym turnieju istnieje zwycięzca lub istnieje trójkąt.

Rozwiązanie

Niech $|M$ będzie zawodnikiem, który wygrał maksymalną liczbę meczów. Jeśli wygrał wszystkie, jest zwycięzcą. W przeciwnym wypadku istnieje zawodnik $W,$ który wygrał z $|M$ oraz istnieje przynajmniej jeden zawodnik pokonany przez $|M.$

Gdyby gracz $|W$ zwyciężył ze wszystkimi, którzy przegrali z $|M,$ to $|W$ wygrałby więcej meczów niż $M$ (bo pokonał też $M$ ) - sprzeczność. Zatem $W$ przegrał z którymś z graczy, z którymi wygrał $M,$ czyli istnieje trójkąt.

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Okrągły stół i trójkąty»Zadanie 2

o zadaniu...

Zadanie pochodzi z artykułu Okrągły stół i trójkąty
Publikacja w Delcie: grudzień 2016
Publikacja elektroniczna: 30 listopada 2016
Artykuł źródłowy w wersji do druku [application/pdf]: (62 KB)

Wykaż, że jeśli w turnieju nie ma trójkąta, to wszystkich graczy można ustawić w rzędzie tak, że każdy wygrał ze wszystkimi zawodnikami stojącymi za nim.

Rozwiązanie

Z zadania 1 wiemy, że skoro nie ma trójkąta, to istnieje zwycięzca $Z1$ ; ustawmy go na początku rzędu. W gronie pozostałych graczy również nie ma trójkąta, więc istnieje gracz $|Z2,$ który pokonał ich wszystkich (ale nie $Z1$ ) - ustawmy go na drugim miejscu rzędu. Kolejnych graczy ustawiamy analogicznie.

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Okrągły stół i trójkąty»Zadanie 3

o zadaniu...

Zadanie pochodzi z artykułu Okrągły stół i trójkąty
Publikacja w Delcie: grudzień 2016
Publikacja elektroniczna: 30 listopada 2016
Artykuł źródłowy w wersji do druku [application/pdf]: (62 KB)

Udowodnij, że jeśli w turnieju istnieje cykl o więcej niż trzech graczach, to istnieje trójkąt.Udowodnij, że jeśli w turnieju istnieje cykl o więcej niż trzech graczach, to istnieje trójkąt.

Rozwiązanie

Niech $|A1$ będzie cyklem, gdzie $|k > 3.$ Rozważmy mecz $A1$ Jeśli wygrał go gracz $A3,$ otrzymujemy trójkąt $A1A2A3.$ W przeciwnym przypadku otrzymujemy cykl $|A$ o $|k− 1$ graczach. Jeśli jest ich więcej niż 3, postępujemy dalej analogicznie.

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Okrągły stół i trójkąty»Zadanie 4

o zadaniu...

Zadanie pochodzi z artykułu Okrągły stół i trójkąty
Publikacja w Delcie: grudzień 2016
Publikacja elektroniczna: 30 listopada 2016
Artykuł źródłowy w wersji do druku [application/pdf]: (62 KB)

Udowodnij, że po każdym turnieju albo można wszystkich uczestników ustawić w cykl, albo można ich tak podzielić na dwie grupy $𝒢$ i $|𝒟,$ że każdy z grupy $|𝒢$ wygrał z każdym z grupy $𝒟.$

Rozwiązanie

Rys. 2

Jeśli nie ma żadnych cykli, to nie ma trójkątów i na mocy zadania 1 istnieje zwycięzca. Wówczas niech grupa $𝒢$ składa się tylko z niego, a grupa $|𝒟$ z pozostałych zawodników.

Jeśli istnieją cykle, to rozważmy cykl $|𝒞$ o maksymalnej długości. Jeżeli $|𝒞$ zawiera wszystkich graczy, to teza jest spełniona. W przeciwnym przypadku istnieje osoba $, |X$ która nie należy do cyklu $𝒞.$ eśli istnieją cykle, to rozważmy cykl $𝒞$ o maksymalnej długości. Jeżeli $𝒞$ zawiera wszystkich graczy, to teza jest spełniona. W przeciwnym przypadku istnieje osoba $,X$ która nie należy do cyklu $𝒞.$

Wykażemy, że $X$ albo wygrał ze wszystkimi zawodnikami z $|𝒞,$ albo ze wszystkim przegrał. Załóżmy przeciwnie, że $|X$ przegrał z $Y ,$ ale wygrał z $Z$ z cyklu (Rys. 2). Wówczas w cyklu $𝒞$ na "drodze" od $|Y$ do $|Z$ istnieją tacy dwaj kolejni zawodnicy $|Y′,Z ′,$ że $X$ przegrał z $′ |Y ,$ ale wygrał z $′ Z$ . Wtedy cykl $𝒞$ można wydłużyć, dołączając zawodnika $X$ pomiędzy $|Y′$ a $Z ′$ (Rys. 3), sprzecznie z założeniem o maksymalności $𝒞.$

Jeżeli istnieją zawodnicy $W$ i $P$ spoza cyklu $𝒞,$ którzy odpowiednio wygrali i przegrali ze wszystkimi z cyklu, to $W$ wygrał z $|P,$ gdyż w przeciwnym razie cykl można by wydłużyć o tych dwóch graczy w sposób przedstawiony na rysunku 4.

Niech do grupy $𝒢$ należą wszyscy zawodnicy, którzy wygrali z graczami z $|𝒞,$ do $𝒟$ ci, którzy przegrali z uczestnikami $𝒞.$ Wszystkich graczy z cyklu $𝒞$ dołączmy do dowolnego spośród zbiorów $|𝒢,𝒟.$ W ten sposób otrzymujemy żądany podział.

Zadanie domowe

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Okrągły stół i trójkąty»Zadanie 5

o zadaniu...

Zadanie pochodzi z artykułu Okrągły stół i trójkąty
Publikacja w Delcie: grudzień 2016
Publikacja elektroniczna: 30 listopada 2016
Artykuł źródłowy w wersji do druku [application/pdf]: (62 KB)

Wykaż, że po każdym turnieju wszystkich jego uczestników można ustawić w rzędzie tak, że każdy wygrał z zawodnikiem stojącym bezpośrednio za nim.

Obiekty: Bryły; Wielościany; Całki; Chaos; Fraktale; Ciągi liczbowe; Figury; Okręgi; Wielokąty; Funkcje; Grafy; Grupy; Gry; Konstrukcje; Krzywe; Liczby; Liczby naturalne; Liczby pierwsze; Liczby rzeczywiste; Liczby wymierne; Liczby zespolone; Losowość; Miary; Modele; Nierówności; Pochodne; Podzielność; Powierzchnie; Przekształcenia; Przestrzenie; Rachunki; Równania; Rozmaitości; Strategie; Szeregi liczbowe; Sztuczna inteligencja; Szyfrowanie; Węzły; Wielokąty; Wielomiany; Zbiory

Narzędzia: Indukcja; Jednokładności