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

Rozważmy ciąg oraz dla Zauważmy, że para jest minusjedynkująca dokładnie wtedy, gdy tzn. Jeśli w ciągu jest wyrazów równych 1, to szukana liczba jest równa

a więc jest nie większa od

Uwaga. Można zauważyć, że przyjmując np. dla uzyskujemy dokładnie par minusjedynkujących.

Ponieważ 1 oraz -1 są liczbami nieparzystymi, więc w każdej z par zerujących liczby i są różnej parzystości. To oznacza, że takich par jest co najwyżej tyle, co zbiorów z jedną liczbą parzystą i jedną nieparzystą. Tych ostatnich jest dokładnie

Uwaga. Można zauważyć, że przyjmując np. dla uzyskujemy dokładnie par zerujących.

Odpowiedź (na obydwa pytania):

Oznaczmy przez odpowiedzi na pytania zadane, odpowiednio, w punktach (a) i (b). Bezpośrednio sprawdzamy, że Przyjmijmy dalej, że

W części (a) zauważmy, że w pierwszym przejeździe z prawdopodobieństwem Piotrek od razu zjedzie na parter oraz dla z prawdopodobieństwem znajdzie się na piętrze a zatem w sytuacji, w której średni numer ostatniego piętra, które odwiedzi przed parterem, jest równy Wobec tego

Podobnie w części (b) z prawdopodobieństwem Piotrek zjedzie na parter od razu oraz dla z prawdopodobieństwem znajdzie się w sytuacji, w której oczekiwana liczba dalszych przejazdów jest równa czyli

Nietrudno zauważyć, że wyprowadzone rekurencyjne wzory na oraz są w istocie jednakowe, a zatem Pozostaje rozwiązać tę rekurencję.

Korzystając z wyprowadzonej zależności dla uzyskujemy

skąd po podstawieniu do rekurencji dla mamy

Stąd wobec wynika, że

Uwaga. Czytelnik Oblatany zauważy z pewnością, że wynik, czyli -ta suma częściowa szeregu harmonicznego, jest oczekiwaną liczbą cykli w rozkładzie losowej permutacji zbioru -elementowego. Jeśli ponadto ów Czytelnik należy do zbioru Czytelników Ambitnych, polecamy Mu znalezienie kombinatorycznego uzasadnienia tego związku.

Jedno pytanie to za mało, gdyż dla dowolnego wielomiany i dadzą tę samą odpowiedź. Okazuje się, że dwa pytania są już wystarczające! Na początku Małgosia może zapytać o wartość Jest to suma wszystkich współczynników wielomianu zatem jest nie mniejsza od każdego ze współczynników. Teraz wystarczy poprosić o ; reprezentacja tej liczby w systemie o podstawie da Małgosi szukane współczynniki wielomianu

Niech będzie środkiem okręgów i Zauważmy, że długość odcinka jest malejącą funkcją kąta czyli rosnącą funkcją kąta więc również rosnącą funkcją odległości punktu od prostej Ta odległość jest nie większa od długości odcinka i jest równa tylko wtedy, gdy Ta ostatnia równość definiuje nam poszukiwany punkt

Zauważmy, że jeśli na ścianach pierwszej kości mam oczek, a na ścianach drugiej kości mam oczek , to prawdopodobieństwo uzyskania sumy oczek równej jest równe współczynnikowi przy w wielomianie

Mamy

W tej sytuacji kości, na których ściankach znajdują się następujące sekwencje oczek: oraz spełniają warunki zadania.