Delta mi!

Niech będzie tą osobą, która uczestniczyła w dokładnie dwóch występach. Przyjmijmy, że to pani; jej mąż otrzymuje oznaczenie Pozostałe pary małżonków: ; W jednym swoim występie pani musiała się pokazać w towarzystwie połowy tych ludzi; w drugim - z pozostałą połową. Ustalmy oznaczenia tak, że w jednym z tych występów uczestniczyły osoby a w drugim I znów, bez straty ogólności, możemy przyjąć (dla wygody języka), że osoby to panie, a panowie (w kontekście tego zadania szybka zmiana płci to nie problem).

W każdym z pozostałych występów mogły uczestniczyć, oprócz pana co najwyżej dwie osoby - bo gdyby więcej, to byłyby/byliby wśród nich dwie panie lub dwaj panowie; a przecież one/oni już się pokazali wspólnie, wraz z panią

Każda para gdzie musiała raz wspólnie wystąpić; i były to różne występy. Jest 30 takich par. Uwzględniając dwa występy z udziałem pani widzimy, że liczba występów musiała wynieść co najmniej 32.

Czy realizacja tej wartości jest wykonalna? Trzeba zapewnić panu wspólne uczestnictwo z każdą osobą poza panią Uzyskamy to, dołączając go (na przykład) do par Zostaną przez to spełnione wszystkie wymagane warunki. Tak więc szukane minimum wynosi 32.

Rozważmy następujące doświadczenie losowe: rzucamy niesymetryczną monetą tak długo, aż wyrzucimy orła po raz -szy. W pojedynczym rzucie prawdopodobieństwo wyrzucenia orła jest równe Z prawdopodobieństwem takie doświadczenie zakończy się po skończonej liczbie rzutów. Z drugiej strony prawdopodobieństwo zakończenia doświadczenia po dokładnie rzutach wynosi

W takim razie

Dla suma równa jest W kolejnych wierszach, na mocy suma liczb jest dwukrotnością sumy poprzedniego wiersza, uzyskujemy więc kolejne potęgi dwójki.

Suma dla parzystych równa jest sumie dla nieparzystych (i równa sumie wyrazów poprzedniego wiersza). Stąd różnica tych dwóch sum daje zero.

Sumujemy wyrazy jak na rysunku 4, od góry, korzystając z

Z rysunku i z poprzedniego zadania otrzymujemy

Element jest środkowym wyrazem wiersza numer Na mocy jest on sumą dwóch wyrazów nad nim, a więc też sumą trzech wyrazów o dwa wiersze wyżej, przy czym środkowy z nich liczymy dwukrotnie. Stąd jest także sumą czterech środkowych wyrazów jeszcze wyższego wiersza, liczonych z krotnościami odpowiednio 1, 3, 3, 1, itd. Na rysunku 5 zilustrowano uzyskane w ten sposób dwa "przenikające się" trójkąty Pascala - wyjściowy oraz drugi "do góry nogami", oznaczający krotności, z jakimi liczyć należy wyrazy z coraz wyższych wierszy.

Trójkąty te mają wspólny -ty wiersz i stąd jest sumą wyrazów tego wiersza, liczonych z krotnościami odpowiadającymi im samym, co kończy dowód.

Każdy wiersz i kolumnę naszej tablicy będziemy nazywali linią. Niech będzie najmniejszą liczbą, dla której istnieje linia złożona z liczb nie większych od Możemy zakładać, że tą linią jest pierwszy wiersz, a jego pierwszym wyrazem jest

Wykażemy najpierw, że w każdej kolumnie, począwszy od drugiej, istnieją takie dwa jej kolejne wyrazy i że i Dla ustalenia uwagi weźmy drugą kolumnę. Jej pierwszy wyraz nie może być większy od Niech będzie najwyżej położonym wyrazem drugiej kolumny, który jest większy od (musi taki istnieć wobec definicji ). Wyraz położony nad jest szukanym

W ten sposób otrzymaliśmy par liczb Największa spośród liczb musi więc wynosić co najmniej W takim razie oraz są poszukiwanymi liczbami.

Ponieważ to iloczyn wszystkich wyrazów ciągu nie zmienia się po wykonaniu ruchu. W szczególności każdy z wyrazów ciągu jest ograniczony z góry przez i ograniczony z dołu przez Ponadto w każdym ruchu, modyfikującym pewne wyrazy o indeksach liczba jest zamieniana na większą liczba zaś - na mniejszą Żaden wyraz ciągu nie może być nieskończenie wiele razy zmniejszany (jako ograniczony z dołu przez ) ani zwiększany (jako ograniczony z góry przez ). W takim razie każdy wyraz zostanie zmieniony skończenie wiele razy, czyli nie możemy wykonać nieskończenie wielu ruchów.

Zauważmy, że suma liczb napisanych na tablicy zmienia się w ciągu ruchu o czyli o liczbę parzystą. Stąd parzystość sumy liczb napisanych na tablicy nie zmienia się, więc nie możemy uzyskać trójki 20, 21, 24.

Ten niezmiennik nie rozstrzyga odpowiedzi na drugie pytanie, ale nietrudno sprawdzić, że wartość nie zmienia się przy zamianie na Ponieważ dla trójki 11, 12, 13 ta wartość wynosi -428, a dla trójki 20, 21, 23 wynosi ona -1356, to również tej trójki nie możemy uzyskać na tablicy.

Odp. Tak!
Oznaczmy chłopców a dziewczyny - Niech dla każdego chłopiec zadzwoni do oraz (gdzie i ). Wówczas zostanie wykonanych łącznie połączeń i pierwszy warunek będzie spełniony w sposób oczywisty. Aby sprawdzić drugi warunek, spójrzmy na tabelę połączeń ("1" oznacza, że zadzwoni do ).

Gdyby drugi warunek nie był spełniony, to na wszystkich 4 wierzchołkach pewnego prostokąta byłyby jedynki, a to nie ma miejsca (między jedynkami w jednym wierszu odległości mogą wynosić odpowiednio 1 lub 9, 2 lub 8 i 3 lub 7, a każda z tych odległości jest realizowana przez co najwyżej jedną parę jedynek).

a) Pewien wierzchołek otrzymuje nazwę Idąc od do wzdłuż brzegu wielokąta, w wybranym kierunku, mijamy kolejno wierzchołki Przechodzimy przez dalej mijamy wierzchołki i wracamy do Numery oraz tworzą permutację zbioru Liczby, przyporządkowane wszystkim bokom, sumują się do wartości

Równość w tym szacowaniu jest osiągalna; ma ona miejsce wtedy i tylko wtedy, gdy oraz Zatem to szukane minimum.

b) Zbiór może być dowolnym podzbiorem zbioru (również pustym, wtedy pierwszy składnik rozpisanej sumy ma postać ). Zauważmy teraz, że już sam wybór zbioru determinuje ponumerowanie, realizujące równość ; liczby ze zbioru uporządkowane rosnąco, trzeba przypisać kolejnym wierzchołkom (przy obieganiu wielokąta od w wybranym kierunku), następny wierzchołek trzeba nazwać a dalszym wierzchołkom dać niewykorzystane numery, uporządkowane malejąco.

Konkluzja: jest tyle możliwości optymalnego ponumerowania wierzchołków, ile podzbiorów ma zbiór to znaczy

Najpierw pokażemy, że połączeń wystarczy. Ustalmy pewną osobę Najpierw każda z pozostałych osób dzwoni do przekazując jej swoją informację. Wówczas osoba zna już wszystkie informacje i w ciągu kolejnych rozmów może przekazać je pozostałym.

Teraz pokażemy, że aby wszyscy poznali wszystkie informacje, potrzeba co najmniej połączeń. Niech oznacza liczbę wszystkich wykonanych w tym celu połączeń, zaś - liczbę połączeń, które zostały wykonane przed pierwszym momentem, gdy pewna osoba (nazwijmy ją ) znała wszystkie wiadomości. Każda z pozostałych osób musi być poinformowana o wiadomościach, których nie zna, więc trzeba wykonać jeszcze co najmniej połączeń, tzn. Zauważmy również, że po telefonach osoba zna wszystkie wiadomości, więc każda z pozostałych osób musiała wykonać wcześniej przynajmniej jedno połączenie (inaczej jej wiadomość nie byłaby znana nikomu poza nią, w szczególności ). Stąd W takim razie

Oznaczmy drużyny przez Niech w -tej rundzie (dla ) drużyny i (dla ) grają ze sobą, jeśli jest podzielne przez zaś drużyny i (dla ) - jeśli jest podzielne przez

Dla ustalonych dokładnie jedna spośród kolejnych liczb jest podzielna przez więc i zagrają ze sobą w dokładnie jednej z rund. Podobnie drużyny i dla zagrają ze sobą dokładnie raz, ponieważ dokładnie jedna z liczb jest podzielna przez

Ustalmy rundę Gdyby drużyna grała w -tej rundzie dwa razy, to dla pewnych liczba byłaby podzielna przez Ponieważ jest parzyste, dostalibyśmy, że co jest niemożliwe. Gdyby drużyna grała dwa razy w -tej rundzie, to zachodziłaby jedna z dwóch możliwości: 1) drużyna gra z drużynami skąd a to jest niemożliwe; 2) drużyna gra z drużynami i skąd co również jest niemożliwe.

W takim razie zaproponowany podział na rundy spełnia warunki zadania.

Nie, Maja może zastosować następującą strategię, która gwarantuje jej zwycięstwo. W pierwszych swoich ruchach Maja maluje na kolorowo punktów z jednej prostej. Każdą parę takich kolorowych punktów można na dwa sposoby uzupełnić do trójkąta równobocznego, par punktów spośród jest więc łącznie po ruchach na płaszczyźnie jest takich punktów, że pomalowanie dowolnego z nich na kolorowo da Mai zwycięstwo.

Dla mamy zatem Gucio nie może w swoich początkowych ruchach wszystkich opisanych powyżej punktów pomalować na czarno i Maja może wygrać w ruchu numer

Narysujmy 3 poziome proste, 9 pionowych i rozważmy 27 punktów ich przecięć. Każdy punkt pomalowano jednym z dwóch kolorów, łącznie jest więc możliwych układów kolorów trójki wyróżnionych punktów z pojedynczej pionowej prostej. Ponieważ mamy 9 pionowych prostych, na pewnych dwóch z nich (nazwijmy je i ) jest ten sam układ kolorów takiej trójki.

Wśród trzech wyróżnionych punktów na prostej pomalowanych dwoma kolorami, pewne dwa punkty mają ten sam kolor. Niech to będą dwa wierzchołki szukanego prostokąta, pozostałe dwa to odpowiadające im punkty tego samego koloru z prostej (leżą one na tych samych poziomych prostych).

Wystarczy uogólnić rozwiązanie poprzedniego zadania i rozważyć prostych poziomych oraz prostych pionowych.

Istnieje kolor, którym pomalowano przynajmniej pól. Rozważmy 48 pól tego właśnie koloru i niech oznacza liczbę tych pól występujących w -tym wierszu; oczywiście W każdym wierszu dwa spośród rozważanych pól można wybrać na sposobów. Wobec tego

przy czym nierówność wynika z nierówności średnich (na marginesie). Tymczasem dwie z 12 kolumn można wybrać na sposobów - mniej niż 72. Oznacza to, że w pewnych dwóch wierszach można wybrać po dwa pola tego samego koloru i w tych samych kolumnach; ich środki tworzą szukany prostokąt.

Uwaga
Dla dowolnych liczb zachodzi nierówność między średnią kwadratową a arytmetyczną:

Ustalmy jednego z rycerzy; powiedzmy, że ma on na imię Lancelot. Rozważmy dwa przypadki.

• Lancelot został wybrany do drużyny. Wówczas żaden z jego dwóch sąsiadów nie będzie w drużynie. Z pozostałych osób musimy wybrać które nie siedzą na sąsiadujących miejscach. Możemy to zrobić na sposobów, ponieważ wybrane osoby jednoznacznie odpowiadają miejscom, a więc wstawieniu pomiędzy miejsc osób spoza drużyny (lub przed pierwszym z nich, lub za ostatnim) miejsc dla osób z drużyny.
• Lancelot nie został wybrany. Spośród pozostałych osób musimy wybrać niebędących wrogami. W tym przypadku drużynę można wybrać na sposobów: pomiędzy miejsc dla osób spoza drużyny (lub przed pierwszym z nich, lub za ostatnim) wstawiamy miejsc dla osób z drużyny.

Odp. Drużynę można więc wybrać na sposobów.

Wykażemy, że jeżeli każdy element zbioru pokolorujemy na jeden z czterech kolorów w sposób losowy, to prawdopodobieństwo zdarzenia, w którym żaden rosnący -wyrazowy ciąg arytmetyczny o wyrazach z tego zbioru nie składa się z elementów o jednakowym kolorze, jest dodatnie. Zakładamy przy tym, że każdy element malujemy na dowolny z czterech kolorów z prawdopodobieństwem i że losowania są niezależne.

Ustalmy chwilowo pojedynczy -wyrazowy ciąg arytmetyczny. Jest wszystkich możliwych pokolorowań tego ciągu, z których dokładnie składają się wyłącznie z elementów o jednakowym kolorze. Prawdopodobieństwo tego, że ustalony ciąg składa się z elementów o jednakowym kolorze, wynosi zatem Oszacujmy od góry liczbę wszystkich rosnących -wyrazowych ciągów arytmetycznych o wyrazach w danym zbiorze. Każdy taki ciąg jest wyznaczony przez swój wyraz początkowy oraz różnicę Spełnione są przy tym nierówności oraz czyli Dla ustalonego istnieje więc co najwyżej ciągów, których pierwszym wyrazem jest Otrzymujemy zatem nierówność

Ponumerujmy wszystkie z rozważanych ciągów w sposób dowolny i dla oznaczmy przez zdarzenie, w którym -ty ciąg zawiera elementy wyłącznie jednego koloru. Z podstawowej własności prawdopodobieństwa (tzw. subaddytywności) otrzymujemy wówczas

Prawdopodobieństwo zdarzenia, w którym pewien ciąg pomalowany został z użyciem wyłącznie jednego koloru, jest mniejsze niż Prawdopodobieństwo dopełnienia tego zdarzenia jest więc dodatnie, co oznacza, że w pewnym kolorowaniu żaden z rozważanych ciągów nie jest jednokolorowy.

Rozważmy takie losowanie par różnych komisji, że dla dowolnych dwóch par prawdopodobieństwo ich wylosowania jest jednakowe. Wylosujmy w ten sposób pewną parę komisji i oznaczmy przez liczbę wspólnych członków tej pary. Niech będzie funkcją charakterystyczną -tej osoby, czyli jeżeli -ta osoba należy do obu wylosowanych komisji oraz w przeciwnym przypadku. Funkcje oraz są zmiennymi losowymi. Ponieważ więc zachodzi równość Jednocześnie wprost z definicji wartości oczekiwanej wynika, że liczba jest w rzeczywistości prawdopodobieństwem tego, że -ta osoba należy do obu z wylosowanych komisji. Jeśli przez oznaczymy więc liczbę komisji, do których należy -ta osoba ze stowarzyszenia, to zachodzi równość

Skoro każda komisja zawiera członków, to mamy ponadto Wykorzystując nierówność między średnią arytmetyczną a kwadratową, otrzymujemy

Zmienna losowa przyjmuje wyłącznie wartości całkowite, a więc skoro jej wartość oczekiwana jest większa niż to co najmniej raz przyjmuje ona wartość nie mniejszą niż Istnieje więc para różnych komisji, która ma przynajmniej czterech wspólnych członków.

Niech oznacza liczbę w -tym wierszu i -tej kolumnie naszej tablicy,

Wybrane liczby można zapisać jako gdzie to pewna permutacja zbioru Suma wybranych liczb wynosi w takim razie

Niech oznacza dany ciąg. Niech dla - ta równość definiuje jednoznacznie liczbę Dla ciągu ruch polega na zamianie jego dwóch wyrazów znajdujących się w odległości lub Jeśli umiemy posortować drugi ciąg, to pierwszy też. Definiujemy ciąg przyjmując, że gdzie oznacza tę liczbę spośród dla której różnica jest podzielna przez Ponieważ więc ciąg to permutacja ciągu Ruchy w ciągu odpowiadają zamianie kolejnych wyrazów ciągu Do ciągu można zastosować sortowanie bąbelkowe pozwalające ustawić jego wyrazy w dowolnej kolejności.

Ponumerujmy koszyki: Niech będzie wagą koszyka (tj. łączną wagą kamieni w tym koszyku) w ustalonej chwili. W kolejnym ruchu przekładamy kamień z koszyka do koszyka Niech będzie wagą tego kamienia; postulowany warunek:

Suma kwadratów wag koszyków po wykonaniu ruchu wynosi

Suma kwadratów wag jest więc (ścisłym) półniezmiennikiem: maleje w każdym kroku procedury. Jest tylko skończenie wiele możliwych rozlokowań kamieni w koszykach, więc wartości tego półniezmiennika przebiegają zbiór skończony. Proces musi się zakończyć.

Niech oznaczają liczbę głównych przekątnych odpowiednio o dwóch końcach czerwonych, o dwóch końcach niebieskich i o końcach w różnych kolorach. Ponieważ każdy wierzchołek jest końcem dokładnie jednej głównej przekątnej, więc mamy czerwonych wierzchołków i niebieskich. Ponieważ liczby te są równe, otrzymujemy