Delta mi!

Niech będzie dowolnym zawodnikiem, który wygrał najwięcej meczów. Udowodnimy, że jest mistrzem.

Oznaczmy przez zbiór zawodników, którzy przegrali z a przez zbiór zawodników, którzy wygrali z Jeżeli zbiór jest pusty, to wygrał ze wszystkimi bezpośrednio, więc jest mistrzem.

Przypuśćmy, że istnieje zawodnik który wygrał z każdym zawodnikiem z Wówczas wygrał ze wszystkimi zawodnikami pokonanymi przez oraz z samym więc ma na koncie więcej zwycięstw niż a to przeczy wyborowi zawodnika Wobec tego dla każdego istnieje o tej własności, że wygrał z a to oznacza, że jest mistrzem.

a) Przypuśćmy, że w pewnym -turnieju jest dokładnie dwóch mistrzów i oznaczmy ich przez w taki sposób, że wygrał z

Niech będzie zbiorem zawodników, którzy wygrali z a - zbiorem zawodników, którzy przegrali z Skoro jest mistrzem oraz to istnieje zawodnik pokonany przez który wygrał z - wynika stąd w szczególności, że zbiór jest niepusty.

Ograniczając turniej do meczów rozegranych między zawodnikami ze zbioru możemy na mocy poprzedniego zadania wskazać zawodnika który jest mistrzem w zbiorze Zawodnik wygrał pośrednio lub bezpośrednio ze wszystkimi pozostałymi zawodnikami w oraz wygrał bezpośrednio z więc wygrał pośrednio ze wszystkimi zawodnikami w To oznacza, że jest mistrzem w całym turnieju, co przeczy założeniu, że mistrzów jest dokładnie dwóch.

b) Rozważmy turniej, w którym są takimi zawodnikami, że wygrał z wygrał z oraz wygrał z a każdy z pozostałych zawodników przegrał z każdym spośród (wyniki meczów pomiędzy tymi zawodnikami mogą być dowolne). W tym turnieju są jedynymi mistrzami (nikt z pozostałych nie wygrał z żadnym z nich) i jest ich trzech.

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

Spośród wszystkich par wyróżnionych punktów o tym samym numerze wybierzmy taką, że między nimi jest jak najmniej innych wyróżnionych punktów (na pewnym z dwóch łuków). Bez straty ogólności przyjmijmy, że wybrana para ma numery 1 (cykliczne przenumerowanie jednocześnie w obrębie punktów obydwu kolorów nie ma wpływu na tezę

Zauważmy, że wszystkie wyróżnione punkty pomiędzy tymi o numerze 1 są tego samego koloru - w przeciwnym przypadku wśród nich byłyby punkty o tym samym numerze. Przypuśćmy, że są to punkty białe; rozumowanie w przypadku punktów czarnych jest analogiczne. W zależności od położenia punktów o numerze 1 możemy wyróżnić dwa przypadki.

Pomiędzy punktami o numerze 1 znajdują się punkty białe o numerach od 2 do Wówczas wybierając jeden punkt podziału okręgu na łuki pomiędzy białymi punktami o numerach i a drugi - w taki sposób, aby na obydwu uzyskanych łukach było po wyróżnionych punktów, uzyskujemy rozcięcie o postulowanej własności.

Pomiędzy punktami o numerze znajdują się punkty białe o numerach od do Wówczas wybierając jeden punkt podziału okręgu na łuki pomiędzy białymi punktami o numerach i (a drugi odpowiednio jak wyżej), uzyskujemy rozcięcie spełniające warunki zadania.

Odpowiedź: Największa możliwa liczba elementów zbioru jest równa

Przyjmując

mamy oraz suma każdych trzech elementów jest większa od a zatem nie należy do

Z drugiej strony, zbiory oraz

(dla ) stanowią rozbicie zbioru a w każdym z nich jeden z elementów jest sumą trzech innych, mianowicie

oraz

Pozostaje zauważyć, że jeżeli oraz to dla pewnego i w konsekwencji zbiór nie ma danej w treści zadania własności.

Przypuśćmy, że każda osoba w danej grupie ma co najwyżej czterech znajomych. Wówczas łączna liczba relacji znajomości w tej grupie nie przekracza

Tymczasem, w myśl warunków zadania, w każdej z piątek osób są co najmniej trzy znajomości, a każda taka trójka znających się nawzajem osób należy do dokładnie piątek osób. Wobec tego łączna liczba znajomości w grupie jest nie mniejsza od

Uzyskana sprzeczność oznacza, że w danej grupie musi istnieć osoba, nazwijmy ją która ma co najmniej znajomych. Aby zakończyć rozwiązanie, wystarczy stwierdzić, że wśród znajomych osoby pewnych trzech zna się wzajemnie, więc dołączając do nich otrzymujemy czwórkę osób o postulowanej własności.

Suma wszystkich wpisanych liczb jest dodatnia, zatem co najmniej jeden wiersz oraz co najmniej jedna kolumna musi mieć sumę dodatnią. W rozważanym ciągu sum (wierszy i kolumn) może więc być co najwyżej liczb ujemnych.

Dla każdego nieparzystego ta wartość jest osiągalna. Ilustracja przedstawia przykładową realizację, gdy Opis algorytmu: cały skrajny dolny wiersz oraz całą skrajną prawą kolumnę wypełniamy jedynkami. Po odcięciu tego fragmentu zostaje plansza kwadratowa o boku długości parzystej W jej górnym wierszu umieszczamy, kolejno od lewej, jedynek oraz minus jedynek. W kolejnych wierszach (planszy ) powtarzamy ten układ z przesunięciem (w każdym kroku) o jednostkę w prawo; nadwyżkę wychodzącą poza prawy skraj przenosimy przy tym cyklicznie na skrajne lewe pole.

W pełnej planszy uzyskujemy przewagę minusów nad plusami we wszystkich wierszach i kolumnach z wyjątkiem ostatniego i ostatniej. Każdy z początkowych wierszy ma sumę zaś ostatni wiersz ma sumę zatem suma całej tabeli wynosi 1. Stąd, ostatecznie, odpowiedź: szukane maksimum wynosi

Odpowiedź: Na sposobów.

Wiersze i kolumny szachownicy nazwijmy rzędami, a zbiór pól szachownicy po jednym w każdym rzędzie - rozsypem. Rozsyp można wybrać na dokładnie sposobów (np. w -tym wierszu wybieramy na sposobów kolumnę, do której należy pole).

Zauważmy, że układ kamieni spełniający warunki zadania ma w każdym rzędzie albo dokładnie jedno pole z trzema kamieniami, albo dokładnie dwa pola, na których leżą odpowiednio jeden i dwa kamienie. Co więcej, zarówno zbiór pól zawierających lub kamienie, jak i zbiór pól zawierających lub kamienie, jest rozsypem. To oznacza, że z każdym rozłożeniem kamieni można związać (uporządkowaną) parę rozsypów.

Z drugiej strony, mając parę rozsypów, możemy na polach pierwszego z nich ustawić po jednym kamieniu, a na polach drugiego - dołożyć po dwa kamienie. Uzyskany w ten sposób układ będzie spełniał warunki zadania. Ostatecznie więc takich układów jest tyle co par rozsypów, czyli

Oznaczmy liczby wokół okręgu kolejno przez i rozważmy sumy dla Są to dodatnie liczby całkowite mniejsze od 300. Jeśli któraś z tych sum jest równa 200, zadanie jest rozwiązane, podobnie dla sumy 100 (wtedy wszystkie pozostałe wyznaczają szukany łuk).

Jeśli żadna z sum nie jest równa 200 ani 100, to każda z nich przy dzieleniu przez 100 daje jedną z 99 niezerowych reszt. Wówczas pewne dwie sumy oraz dla dają taką samą resztę, więc ich różnica dzieli się przez 100, czyli jest równa 200 lub 100. Podobnie jak powyżej wyznacza ona wobec tego poszukiwany łuk lub jego dopełnienie.

Kolorowe ramki oznaczają żołnierzy wysokich i niskich.

Tak; co więcej, wystarczy ustawić żołnierzy raz w kolumnach i raz w rzędach. Przypuśćmy, że potem w pewnej kolumnie wyższy żołnierz stoi za niższym wbrew żądaniu, że mają stać według wzrostu. Rozważmy żołnierzy stojących w rzędzie z i przed nim (są oni wyżsi od niego, ich wraz z nazwiemy wysokimi) oraz żołnierzy stojących w rzędzie z i za nim (są niżsi od ich wraz z nazwiemy niskimi). Zauważmy, że każdy żołnierz wysoki jest wyższy od każdego z żołnierzy niskich (bo jest wyższy od a - od ). Wysokich i niskich żołnierzy jest łącznie o 1 więcej niż kolumn, więc zanim uporządkowano rzędy, pewnych dwóch z nich stało w tej samej kolumnie. Wysocy stali w różnych kolumnach, niscy też w różnych, stąd w jednej kolumnie musiał stać jakiś żołnierz wysoki za niskim - sprzeczność, bo kolumny były już wtedy uporządkowane.

Każdego żołnierza utożsamiamy z jego wzrostem, a następnie dajemy mu numer - długość najdłuższego rosnącego podciągu w danym szeregu, którego jest on ostatnim elementem. Jeśli któryś żołnierz ma numer 8, mamy szukany podciąg rosnący

W przeciwnym przypadku każdy z 50 żołnierzy ma numer najwyżej 7. Gdyby każdy z numerów od 1 do 7 występował najwyżej 7-krotnie, łącznie mielibyśmy najwyżej 49 żołnierzy. Stąd któraś liczba powtarza się co najmniej 8 razy. Żołnierze o tych właśnie numerach tworzą szukany podciąg malejący, gdyż każdy kolejny z nich jest niższy od poprzednika o tym samym numerze (gdyby bowiem był wyższy, byłby następnym elementem rosnącego podciągu i miałby numer o jeden większy).

Rozważmy liczby Wśród pierwszych z nich pewne dwie dają tę samą resztę z dzielenia przez Ich różnica jest liczbą postaci podzielną przez co kończy dowód.

Udowodnimy, że odpowiednie zaplanowanie rozgrywek jest możliwe dla każdego

Rozważmy ostrosłup prawidłowy -kątny o podstawie i wierzchołku Ponumerujmy zawodników liczbami od do i ustalmy, że zawodnik o numerze w -tej rundzie gra z zawodnikiem o numerze a dla zawodnicy o numerach i grają ze sobą w -tej rundzie wtedy i tylko wtedy, gdy

Łatwo zauważyć, że to poprawnie wyznacza przebieg rozgrywek: pary zawodników grających w każdej z rund są rozłączne, nie powtarzają się w różnych rundach (każdy bok oraz każda przekątna podstawy ostrosłupa jest prostopadła do dokładnie jednego z odcinków ) oraz każda runda składa się z dokładnie partii.

Udowodnimy, że

Oznaczmy krótko jeżeli zawodnik wygrał z zawodnikiem a trójkę zawodników o tej własności, że nazwijmy remisową (trójki utożsamiamy).

Rozważmy turniej szachowy z udziałem zawodników o następujących wynikach:

• ;
• dla ;
• jeżeli to

Wówczas

więc opisany turniej spełnia założenia zadania (zawodnicy mogą usiąść przy okrągłym stole w określonej powyżej kolejności). W takim turnieju są dokładnie trójki remisowe, mianowicie dla co oznacza, że

Dowód nierówności przeprowadzimy indukcyjnie. Dla jest dokładnie jedna trójka remisowa. Przypuśćmy, że liczba trójek remisowych w turnieju z zawodnikami (których można odpowiednio usadzić przy okrągłym stole) jest nie mniejsza od przy czym i rozważmy dowolny turniej z zawodnikami w którym

Jeżeli dla każdego (gdzie oraz ), to każda z trójek jest remisowa, więc jest ich co najmniej (w szczególności więcej niż ).

W przeciwnym przypadku istnieje takie że ; bez straty ogólności (ewentualnie cyklicznie przenumerowując zawodników) przypuśćmy, że Wówczas z założenia indukcyjnego wynika, że tworzą co najmniej różne trójki remisowe. Wystarczy więc wykazać, że istnieje trójka remisowa, do której należy zawodnik Istotnie, skoro oraz to istnieje takie że

na przykład i trójka jest wówczas remisowa. To kończy dowód indukcyjny i rozwiązanie zadania.

Zauważmy, że dla każdego a także

gdyż każda strona powyższej równości jest równa liczbie wszystkich rozegranych partii. Wobec tego

skąd wynika postulowana równość.

Na początku połączmy każde dwie kulki nitką. Ilekroć pewną grupę dzielimy na i kulek, przecinamy wszystkie nitek pomiędzy rozdzielanymi kulkami. Kulki pozostające w jednej grupie nadal są połączone. W efekcie, po uzyskaniu pojedynczych kulek, przetniemy wszystkie nitki (i każdą tylko raz), a rozważana suma iloczynów to właśnie liczba tych nitek.

Nie. Gdyby tak było, to liczba uścisków dłoni byłaby równa bo w każdym z nich uczestniczą dwie osoby. Jednak liczba ta nie jest całkowita.

Niech rozważane osoby będą ośmiornicami i niech każda poda jedną kończynę każdej znajomej osobie przeciwnej płci. Wtedy dowolne grono chłopców podaje dziewczętom łącznie kończyn. Jednocześnie każde dziewczę jest w stanie chwycić najwyżej 8 z nich, znajomych dziewczyn musi więc być co najmniej

Gdyby w -osobowej grupie każdy miał inną liczbę znajomych, to byłyby to liczby Nie jest jednak możliwe, by ktoś znał wszystkich pozostałych osób i jednocześnie ktoś inny miał 0 znajomych.

Tak. Wkłada jedną rękawiczkę na drugą i wita się z gościem 1. Następnie zdejmuje zewnętrzną rękawiczkę i wita się z gościem 2. Potem gość 3 wkłada zewnętrzną rękawiczkę (jej wnętrze jest czyste) i wita się z Jasiem.

Do jednej grupy weźmy dowolnych 20 monet i wszystkie je odwróćmy. Drugą grupę niech tworzą pozostałe monety. W obu grupach po tyle samo monet leży teraz orłem do góry, bo jeśli wśród wybranych 20 monet było ich to po odwróceniu jest ich czyli tyle samo, ile wśród pozostałych monet.

Nie. Prosta przecinająca wielokąt na przemian wchodzi do jego wnętrza i z niego wychodzi. Zaczyna i kończy na zewnątrz, przecina więc obwód parzystą liczbę razy.

Gdyby każda średnica o jednym końcu na lądzie miała drugi koniec w wodzie, to łączna powierzchnia lądów byłaby co najwyżej taka, jak wód - sprzeczność.

Funkcja jest reprezentowana przez jej wykres - w tym przypadku układ kropek na "planszy"

(to zbiór punktów kratowych w kwadracie ), po jednej kropce na każdej linii pionowej. Stosując do takiego układu funkcję uzyskujemy przesunięcie wszystkich kropek o jednostkę w dół, z wyjątkiem tych, które już były na dolnej krawędzi; one nie zmieniają położenia. Działanie funkcji jest podobne (ruch w górę; blokada na górnej krawędzi).

Niech będą dwoma różnymi punktami zbioru takimi, że odcinek jest równoległy do przekątnej kwadratu, przy czym punkt leży na prawo i w górę od Dla takiej pary punktów niech oznacza funkcję, której wykres składa się z punktów kratowych, położonych na odcinku poziomym od lewego skraja planszy do na odcinku i na odcinku od do prawego skraja planszy (rysunek obok). Złożenie takiej funkcji z dowolną z operacji daje w wyniku znów funkcję takiej postaci lub funkcję stałą (o wykresie: wszystkie kropki na krawędzi górnej lub dolnej). Złożenie funkcji stałej z lub daje oczywiście także funkcję stałą.

Wniosek: startując od odwzorowania tożsamościowego i stosując skończenie wiele razy operacje (w dowolnej kolejności) możemy uzyskać tylko funkcje typu oraz funkcje stałe. Co ważne, każdą taką funkcję da się w ten sposób uzyskać (przykładową ewolucję przedstawia rysunek poniżej).

Pozostaje zliczyć funkcje - czyli możliwe pary punktów - oraz doliczyć funkcje stałe. Punkty mogą leżeć na przekątnej (przechodzącej przez punktów kratowych), na jednej z dwóch linii (po punktów kratowych), na jednej z dwóch linii (po punktów kratowych), itd. Liczba możliwych do uzyskania funkcji (więc funkcji stałych oraz wszystkich funkcji ) wynosi zatem