Delta mi!

Zauważmy, że każdy delfin wykonał dokładnie skoków, a zatem żaden z nich nie mógł opłynąć całego basenu. Dla każdego delfina rozważmy skierowany łuk basenu rozpoczynający się w początkowym zbiorniku delfina, a kończący w jego zbiorniku końcowym. Jeżeli delfin wykonał skoków zgodnie z ruchem wskazówek zegara (patrząc na basen od góry), to wykonał skoków w przeciwnym kierunku, a zatem jego łuk ma skierowaną długość Łączna długość wszystkich takich łuków jest równa zero, gdyż przy każdej akrobacji długość łuku jednego z uczestniczących w niej delfinów wzrasta o 1, a drugiego - maleje o 1.

Niech będzie delfinem, który wykonał najwięcej skoków zgodnie z ruchem wskazówek zegara, czyli równoważnie - ma najdłuższy łuk. Zauważmy, że delfin skakał wyłącznie zgodnie z ruchem wskazówek zegara. Rzeczywiście, gdyby skoczył w przeciwnym kierunku podczas wspólnej akrobacji z delfinem to oznaczałoby, że początkowo znajdował się we (zegarowo) wcześniejszym zbiorniku, a końcowo w późniejszym, gdyż była to ich jedyna zamiana. W konsekwencji łuk byłby dłuższy niż łuk co jest sprzeczne z wyborem

Oznaczmy zbiorniki kolejno liczbami 1, 2, zgodnie z ruchem wskazówek zegara, przy czym 1 jest początkowym zbiornikiem delfina Skoro wykonał dokładnie skoków i w każdym z nich numer zbiornika wzrastał o 1, to końcowym zbiornikiem jest Wykażemy, że obręcz między zbiornikami 1 oraz nie została użyta do wykonania żadnej akrobacji.

Przypuśćmy przeciwnie - że w pewnym momencie delfin znajdujący się w zbiorniku 1 zamienił się z delfinem znajdującym się w zbiorniku Ich położenie świadczy o tym, że zamienił się już wcześniej z a - jeszcze nie. Jednak po skoku przez obręcz między zbiornikami 1 i zamiana delfinów i przestanie być możliwa, gdyż skacze tylko zgodnie z ruchem wskazówek zegara. Uzyskana sprzeczność kończy rozwiązanie.

Każdego uczestnika turnieju potraktujmy jako wierzchołek, a każdy mecz jako krawędź pewnego grafu skierowanego skierowaną od zwycięzcy do przegranego. Usadzenie zawodników przy okrągłym stole zgodnie z warunkami zadania jest równoważne istnieniu skierowanego cyklu długości (krótko: -cyklu).

Udowodnimy, że:

• w istnieje 3-cykl;
• jeśli w istnieje -cykl, to istnieje też -cykl, dla

Wyniknie stąd, że w istnieje -cykl, czyli teza zadania.

Niech będzie wyjściowym -cyklem oraz niech będzie najmniejszym indeksem o tej własności, że (zbiór takich indeksów jest niepusty, gdyż należy do niego ). Wówczas więc w istnieje 3-cykl.

Niech będzie pewnym -cyklem, gdzie oraz niech będzie dowolnym wierzchołkiem spoza tego cyklu. Jeśli istnieje takie że to uzyskujemy -cykl poprzez wstawienie pomiędzy oraz (przyjmujemy ). W przeciwnym przypadku są dwie możliwości: dla każdego lub dla każdego ; niech będzie zbiorem wierzchołków pierwszego typu, a - zbiorem wierzchołków drugiego typu.

Gdyby to dla każdego oraz każdego - nie mógłby wtedy jednak istnieć -cykl w Podobnie gdyby to w nie mógłby istnieć -cykl. Również gdyby dla każdej pary to w nie mógłby istnieć -cykl. Stąd wniosek, że istnieją wierzchołki o tej własności, że To oznacza, że istnieje -cykl

(a) Każda osoba zmieniła stół, przy którym siedzi, razy, czyli nieparzystą liczbę razy. Stąd wniosek, że składy osób przy stołach po prostu się zamieniły.

(b) Udowodnimy indukcyjnie, że jest to możliwe dla każdego Przypadek jest łatwy do rozważenia. W przypadku oznaczmy stoły przez i osoby siedzące przy tych stołach odpowiednio przez oraz Rozważmy następujący ciąg zamian. Najpierw zamienia się miejscami kolejno z w wyniku czego następuje pełna zamiana składów przy stołach. Następnie zamienia się miejscami kolejno z w wyniku czego przy stole siedzą osoby oraz a przy stole siedzą osoby oraz Pozostaje zastosować założenie indukcyjne dla wszystkich osób poza i

Odpowiedź: Tak.
Poniższe obrazki ilustrują przykładowy układ rozgrywek spełniających warunki zadania. Punkty oznaczają zawodników, strzałki - mecze (kierunek strzałki odróżnia na każdym korcie połówkę "wskazującą" od "wskazywanej"), a liczby przy strzałkach to numery rund (od 1 do 5), w których rozgrywane są odpowiednie mecze.

Odpowiedź: Nie.
Przypuśćmy, że się udało, i rozważmy sytuację po rozegraniu pierwszej rundy. Nie jest możliwe, że obydwie osoby, które zagrały na ustalonym korcie, na nim zostaną, bo wtedy w drugiej rundzie musiałyby zagrać ze sobą jeszcze raz. Nie jest również możliwe, że obydwaj zawodnicy zmienią kort, bo wówczas w drugiej rundzie znów zagraliby przeciwko sobie (tyle że na innym korcie). Wobec tego na każdym korcie po pierwszej rundzie jeden gracz zostaje (i zmienia połówkę), a jeden zmienia kort. Stąd wniosek, że po drugiej rundzie istnieje zawodnik który dotąd grał tylko na pierwszym korcie, i zawodnik który dotąd grał tylko na drugim korcie. Ci zawodnicy nie grali jeszcze ze sobą, więc powinni zagrać w trzeciej rundzie - ale nie mają gdzie (gdyby zagrali na pierwszym korcie, powtórzyłby połówkę, a gdyby na drugim - powtórzyłby połówkę). Uzyskana sprzeczność oznacza, że nie jest możliwy taki układ rozgrywek.

Niech będzie liczbą uczestników pewnego kółka, spełniającego opisane w zadaniu warunki. Udowodnimy, że Przydatny okaże się następujący lemat, którego dowód można znaleźć na przykład w Wikipedii pod hasłem twierdzenie Ramseya:

Wybierzmy pewnego uczestnika Przypuśćmy, że lubi on pewnych 6 uczestników. Zgodnie z założeniem zadania oraz powyższym lematem wśród nich znajduje się 3, którzy wzajemnie się lubią, i razem z tworzą oni czwórkę, która przeczy założeniom zadania. Przypuśćmy teraz, że nie lubi pewnych 4 uczestników. Wśród nich znajduje się dwóch, którzy się nie lubią, i razem z tworzą oni trójkę sprzeczną z założeniami. Wynika stąd, że Gdyby jednak to każdy uczestnik musiałby lubić dokładnie 5 uczestników. Jest to sprzeczność, gdyż suma liczb sympatii poszczególnych uczestników wyniosłaby 45, a musi to być liczba parzysta ze względu na wzajemność uczuć. W tej sytuacji

Jeśli ponumerujemy 8 uczniów liczbami od 1 do 8 i okaże się, że uczniowie o numerach i lubią się tylko wtedy, gdy to ta grupka będzie spełniać warunki zadania, co kończy rozwiązanie.

Teza wynika wprost z tego, że mnożenie przez element niezerowy jest bijekcją ciała W języku bardziej elementarnym: jeśli jest permutacją zbioru zaś jest elementem zbioru to reszty z dzielenia liczb przez są wszystkie różne - tworzą więc także permutację zbioru Przy tym jeśli wyjściowa permutacja należała do zbioru - czyli spełniała zależność (mod ) - to po pomnożeniu wszystkich jej wyrazów przez utworzy permutację, w której analogiczna suma przystaje do - czyli permutację należącą do zbioru

Zostało w ten sposób określone odwzorowanie ze zbioru do zbioru Ono jest odwracalne; weźmy bowiem element dla którego (mod ) (taki element istnieje, bo reszty z dzielenia liczb przez są wszystkie różne i niezerowe). Jeśli teraz permutacja znajduje się w zbiorze to po pomnożeniu wszystkich wyrazów przez znajdzie się w zbiorze Uzyskane odwzorowania (mnożenie przez ) oraz (mnożenie przez gdzie ) są wzajemnie odwrotne. To dowodzi, że zbiór jest równoliczny ze zbiorem Skoro tak jest dla każdej niezerowej reszty znaczy to, że wszystkie zbiory są równoliczne.

Niech i będą odpowiednio liczbami dziewczynek i chłopców startujących z -tej szkoły. Niech ponadto będzie liczbą singli, a liczbą miksów. Wówczas

skąd

gdzie Z założeń zadania

a zatem

Oznacza to, że co najwyżej trzy spośród liczb są różne od 0, co kończy rozwiązanie.

Niech dla będzie liczbą elementów zbioru pomalowanych na biało. Zauważmy, że jest liczbą elementów zbioru pomalowanych na biało, czyli Jeśli to teza zadania zachodzi. W przeciwnym razie albo Przyjmijmy bez straty ogólności, że spełniony jest pierwszy przypadek (drugi jest analogiczny). Wtedy Jest jasne, że zatem istnieje taka liczba dla której mamy co jest równoważne z tezą zadania.

W każdym wierszu środkowy wyraz jest liczbą nieparzystą (oczywista indukcja); wraz ze skrajnymi jedynkami daje to już trzy liczby nieparzyste w wierszu. Dla kontroli parzystości pozostałych elementów użyjemy modelu algebraicznego. Traktujemy wyrazy -tego wiersza jako kolejne współczynniki wielomianu stopnia Mnożąc ów wielomian przez trójmian otrzymujemy wielomian stopnia którego kolejnymi współczynnikami są wyrazy następnego wiersza tabeli - bo taka jest zasada generowania kolejnych wierszy. Stąd wniosek, że wyrazy -tego wiersza to kolejne współczynniki wielomianu zapisanego w postaci rozwiniętej.

Zauważmy, że jeśli to wyrazy -tego wiersza, poza wspomnianymi trzema, są liczbami parzystymi. Uzasadnienie indukcyjne: tak jest dla ; i jeśli tak jest dla to podnosząc wielomian do kwadratu dostajemy wielomian utworzony przez kwadraty składników wielomianu (ich współczynniki nie zmieniają parzystości) plus liczne podwojone iloczyny, dające współczynniki parzyste.

Ustalmy teraz liczby całkowite oraz przy czym Wykażemy, że w wierszu o numerze na pozycji znajduje się liczba nieparzysta, zaś na pozycji liczba parzysta.

Zapiszmy wielomiany w postaci rozwiniętej:

Współczynnik wyraża się wzorem

Wszystkie liczby w nawiasie są parzyste (jako współczynniki wielomianu z pozycji nie skrajnych ani nie środkowej); liczba jest nieparzysta (środkowy wyraz ). Zatem liczba jest nieparzysta.

Na pozycji widzimy w wielomianie współczynnik

tutaj nieparzyste czynniki mamy tylko dla oraz (środkowy wyraz w ); towarzyszą im czynniki oraz Te dwie liczby są położone w wierszu symetrycznie względem wyrazu środkowego więc są równe.

Z wykazanych własności wynika zarówno teza (a) (którą zresztą można uzyskać wieloma innymi metodami), jak i odpowiedź na pytanie (b): dokładnie trzy liczby nieparzyste są tylko w wierszach o numerach (bowiem gdy nie jest potęgą dwójki, znaleziona liczba nieparzysta leży w wierszu na pozycji więc nie na skraju ani nie na środku).

Zauważmy, że każdej parze atakujących się wież odpowiadają dokładnie trzy linie, w których nie znajdują się żadne inne wieże - mianowicie te linie, w których te dwie wieże się znajdują. Wobec tego liczba par wież nie przekracza . Ponadto w każdej linii mogą pojawić się co najwyżej dwie wieże. Łącząc powyższe obserwacje, uzyskujemy, że liczba wież nie przekracza

Udowodnimy, że powyższe wyrażenie w istocie zadaje największą możliwą liczbę wież. Przypuśćmy, bez straty ogólności, że oraz, że to liczba kolumn, a - liczba wierszy. Nietrudno wskazać przykład, że jeśli , to można osiągnąć ustawienie wież. Jeżeli , to w wierszach umieszczamy po dwie wieże, tym samym redukując szachownicę do kwadratu o boku i wobec obserwacji z poprzedniego zdania, znów otrzymujemy ustawienie realizujące wież. Wreszcie dla ustawiamy po dwie wieże w każdym wierszu i otrzymujemy ustawienie wież.

Ustawmy na zewnątrz szachownicy, wzdłuż jej boków, dodatkowe wież (po jednej na każdą jednostkę obwodu szachownicy). Zauważmy, że każda prawdziwa wieża jest atakowana przez dokładnie dwie wieże dodatkowe. Stąd wniosek, że liczba wież prawdziwych nie przekracza połowy liczby wież dodatkowych, czyli . Ustawiając wieże w czterech narożnikach szachownicy oraz wzdłuż dwóch jej prostopadłych boków, uzyskujemy przykład realizujący to szacowanie.

Każde z pól szachownicy przylegających do jej brzegu nazwijmy brzegowym. Zauważmy, że każda wieża, która sama nie znajduje się na polu brzegowym, atakuje dokładnie jedno puste (czyli niezajęte przez inną wieżę) pole brzegowe. Wobec tego łączna liczba wież jest nie większa od liczby pól brzegowych. Z drugiej strony, ustawiając wieże na wszystkich polach brzegowych, uzyskujemy konfigurację, która spełnia warunki zadania.

Niech będzie zbiorem punktów o współrzędnych należących do zbioru Niech będzie zbiorem punktów należących do których co najmniej jedna współrzędna jest równa 1. Wówczas w nie ma 4 punktów będących wierzchołkami równoległoboku, zatem szukana liczba nie przekracza liczności czyli

Rozważmy dowolny podzbiór zbioru Przypuśćmy, że w nie ma 4 wierzchołków równoległoboku. Dla niech będzie zbiorem punktów należących do których pierwsza współrzędna wynosi Niech będzie zbiorem odległości "najniższego" punktu zbioru od pozostałych punktów tego zbioru. Wówczas Ponadto, ze względu na przypuszczenie o braku równoległoboku, zbiory muszą być parami rozłączne, a zatem

Jest to sprzeczność, gdyż każdy ze zbiorów jest podzbiorem więc lewa strona powyższej nierówności nie może przekraczać Wobec przedstawionych rozważań odpowiedzią na pytanie z zadania jest

Odpowiedź: oraz
Spośród ośmiu rozważanych sum największa jest z jednej strony nie mniejsza od a z drugiej - nie większa od Stąd wniosek, że Ponadto suma ośmiu rozważanych sum jest równa dwukrotności sumy wszystkich liczb wpisanych w pola tablicy, czyli Liczba jest dzielnikiem tej sumy, wobec czego lub Poniższy przykład pozwala stwierdzić, że te wartości w istocie są osiągalne.

Oznaczmy przez wspólną wartość sumy elementów w obydwu podzbiorach. Wówczas

czyli

Gdyby pewien z rozważanych podzbiorów miał elementów, to jego suma elementów byłaby nie mniejsza od

Uzyskana sprzeczność kończy rozwiązanie zadania.

Odpowiedź: Wszystkie nieparzyste liczby

Z warunków zadania wynika, że każda świeczka wypala się po całkowitej liczbie godzin, powiedzmy Wówczas łączny czas (w godzinach) płonięcia wszystkich świeczek to z jednej strony a z drugiej

skąd i w konsekwencji, aby opisana sytuacja mogła mieć miejsce, musi być liczbą nieparzystą.

Z drugiej strony dla każdej nieparzystej liczby powiedzmy gdzie jest liczbą całkowitą nieujemną, można tak zaplanować, które świeczki będą zapalane danego dnia, aby warunki zadania zostały spełnione. Przykładowo, jeśli ponumerujemy świeczki od do to możemy

• dla : -tego dnia zapalić wszystkie świeczki o numerach od do ;
• dla : -tego dnia zapalić wszystkie świeczki o numerach od do

Zauważmy, że jeśli liczba raz pojawi się na górze stosu, to aby pojawiła się tam ponownie, wcześniej musi się tam znaleźć liczba większa od W szczególności pojawi się na górze co najwyżej raz. Jeśli to nastąpi, to pojawi się później co najwyżej raz, jeżeli nie, to również pojawi się w ogóle co najwyżej raz. Po ewentualnym wystąpieniu liczba pojawi się co najwyżej raz itd. To oznacza, że w pewnym momencie na górze musi pojawić się liczba

Jeżeli jest liczbą nieparzystą, czyli dla pewnej liczby całkowitej to na niebiesko malujemy liczby oraz a na czerwono - wszystkie pozostałe. Wówczas suma czerwonych liczb jest równa

czyli jest równa iloczynowi niebieskich liczb.

Jeśli zaś jest liczbą parzystą, czyli dla pewnej liczby całkowitej to na niebiesko malujemy liczby oraz a na czerwono - wszystkie pozostałe. Wówczas suma czerwonych liczb jest równa

czyli jest równa iloczynowi niebieskich liczb.

Odpowiedź: Nie wynika.

Na poniższym obrazku zilustrowana jest przykładowa sieć znajomości (uczestnikom konferencji odpowiadają punkty, a znajomościom - odcinki), dla której stosowne zakwaterowanie nie istnieje.

Rzeczywiście, niezależnie od sposobu zakwaterowania osoby pozostali uczestnicy dzielą się na dwie grupy -osobowe i jedną -osobową o tej własności, że każdy ma niezakwaterowanych dotąd znajomych tylko w obrębie danej grupy. Żadnej z grup -osobowych nie da się zakwaterować w dwuosobowych pokojach.

Rozważmy usadzenie przy okrągłym stole spełniające opisany w zadaniu warunek. Kolejne pary uczestników siedzących obok siebie przy stole połączmy na zmianę odcinkami czerwonymi i niebieskimi. Ponadto każdego połączmy zielonym odcinkiem z tym znajomym, obok którego nie siedzi. Wystarczy teraz zauważyć, że każdy z trzech użytych kolorów wyznacza inny sposób zakwaterowania.

Przypiszmy drużynom punktów przestrzeni, z których żadne trzy nie leżą na jednej prostej. Jeśli dwie drużyny rozegrały ze sobą mecz pierwszego dnia, połączmy odpowiadające im punkty odcinkiem niebieskim, a jeśli drugiego dnia - odcinkiem czerwonym.

Zauważmy, że uzyskujemy w ten sposób układ łamanych zamkniętych, z których każda ma parzystą liczbę odcinków, gdyż w każdej z nich kolejne odcinki mają różny kolor. Wystarczy z każdej takiej łamanej wybrać co drugi wierzchołek - w ten sposób uzyskamy punktów, z których żadne dwa nie są połączone odcinkiem. Drużyny odpowiadające tym punktom mają więc żądaną własność.

Odpowiedź: maksymalna wartość o jakiej mowa, to Macierz o wyrazach daje przykład wypełnienia planszy, przy którym liczba pojawia się razy (cała jedna przekątna), a żadna liczba nie występuje więcej niż razy. Pozostaje wykazać, że przy każdym wypełnieniu planszy, zgodnym z podanym warunkiem, pewna liczba wystąpi razy.

Weźmy pod uwagę dowolne takie wypełnienie i niech oraz oznaczają najmniejszą oraz największą liczbę w kolumnie Liczby w sąsiednich polach różnią się co najwyżej o 1, więc w -tej kolumnie są wszystkie liczby całkowite z przedziału

Gdy wówczas pewna liczba całkowita należy do wszystkich przedziałów Jest ona obecna we wszystkich kolumnach, więc występuje -krotnie na planszy.

Gdy zaś znaczy to, że dla pewnych numerów kolumn zachodzi nierówność Weźmy dowolny wiersz. Na przecięciu z kolumnami i są w tym wierszu: pewna liczba oraz pewna liczba ; zatem są w tym wierszu wszystkie liczby całkowite z przedziału Wiersz był dowolny, czyli każda z tych liczb (np. ) jest obecna we wszystkich wierszach - występuje wobec tego razy. To uzasadnia odpowiedź.