Zadanie 8 z I etapu 77. Olimpiady Matematycznej — rozwiązanie
Olimpiada Matematyczna⏱ 43 min
Rozwiązanie zadania 8 z I etapu 77. Olimpiady Matematycznej – celowo „pompatyczne”, z użyciem języka teorii grup i rachunku prawdopodobieństwa. Da się bez nich, ale z nimi o zadaniu myśli się dużo łatwiej.
W tym nagraniu
Grupa permutacji Sₙ: składanie, identyczność, elementy odwrotne
Rząd permutacji – dlaczego potęgi f kiedyś się powtarzają
Działanie permutacji na dwuelementowych podzbiorach
Zliczanie przez wartość oczekiwaną i zamianę kolejności sumowania
Rozwiązanie zadania 8 z I etapu 77. Olimpiady Matematycznej (2025/2026), w którym występują permutacje i ich inwersje. Rozwiązanie jest celowo „pompatyczne”: używa języka teorii grup i rachunku prawdopodobieństwa — da się bez nich obejść, ale porządkują myślenie o zadaniu.
Najpierw pokazane jest, że rozważany zbiór permutacji {f₁, …, f_N} tworzy podgrupę grupy permutacji Sₙ: złożenie dwóch jego elementów i element odwrotny znów do niego należą. Pomaga w tym pojęcie rzędu permutacji — kolejne potęgi f, f², f³, … muszą się kiedyś powtórzyć, bo permutacji zbioru n-elementowego jest skończenie wiele.
Kluczowe są dwie obserwacje: jak zmienia się liczba inwersji przy składaniu permutacji i to, że działanie podgrupy na dwuelementowych podzbiorach zachowuje rozkład jednostajny. Wtedy szukaną wielkość można policzyć jako wartość oczekiwaną, zamieniając kolejność sumowania. Na końcu nagrania jest errata do fragmentu z 15:35.
Rozdziały
Kliknij czas, żeby przewinąć nagranie do wybranego fragmentu.
Transkrypt został wygenerowany automatycznie na podstawie napisów YouTube, więc może zawierać błędy w zapisie wzorów, nazwisk i terminów. Kliknij znacznik czasu, aby przewinąć wideo do danego fragmentu. (3362 słów)
Dzisiejszy deadline drugiej serii pierwszego etapu olimpiady matematycznej uczcimy przesadnie pompatycznym rozwiązaniem zadania ósmego i będziemy udawać, że jesteśmy fajni i używać aparatu pojęciowego teorii grup i rachunku prawdopodobieństwa. Da się bez niego przeżyć, ale on ułatwia myślenie o tym zadaniu. Tak. To zacznijmy od tego, że mamy takie coś. Sn to jest grupa permutacji. Dokładnie to jest ten świat, w którym dzieje się zadanie zbioru dietety tak. Oni złołaśliwie w treści zadania napisali, że permutacje to są funkcje różnowartościowe, ale my jesteśmy na tyle dorości, że wiemy, że funkcja różnowartościowa ze spiu skończonego w siebie jest też funkcją na i wyniku tego jest bijekcja.
To, że napisaliśmy grupa, to to znaczy tyle, że w tym zbiorze SN mamy dwa dodatkowe elementy struktury. Mamy składanie oczywiście mam F i G w Sn, to mam tam też złożenie. Będziemy o nim myśleć jako o mnożeniu. I mam jeszcze taki bardzo ważny element. Identyczność. To jest permutacja określona takim wzorem. Bez wątpienia to jest bijekcja i jej robotą jest spełnianie takich praw rachunkowych, że jak się pomnoży z fem z którejkolwiek strony, to wychodzi f.
I co jeszcze? Dla każdego FFS nie mamy takie G bez e nie takie, że F złożone z G to jest to samo co G złożone z F, czyli identyczność i wtedy taki G nazywamy odwrotnością F. To mam na myśli mówiąc grube. I ja bym teraz chciał udowodnić, że jak weźmiemy to, co jest w treści zadania, czyli ten wyróżniony podzbiór wszystkich permutacji, to on jest pod grubą.
Tak to znaczy dla każdych f i g w fie f złożone z g też jest w fie oraz dla każdego fa w fie f do min też jest w to nie jest wielkie odkrycie Pierwszy warunek jest za darmo z treści zadań. No po prostu treść zadania mówi o fch z indeksami. My mówimy o elementach zbioru. Tu tu nie ma żadnej konfuzji między tym, że tam zbiór jest ponumerowany, a tutaj nie. nawet tam powiedzieli, że te indeksy i j y yyy mogą być takie same, czyli te f i g, które są w tym w tym warunku mogą być takie same.
To ten warunek jest z definicji. Tak, to jest bezpośrednio z treści zadania. Jak mamy taki zbiór f, który jest zamknięty na składanie, no to jeśli f jest w fie, no to f złożone z fie, czyli f złożone z fłożone z f. To było w fie, to jest w fie. F jest zamknięty na składanie, więc to też jest w Fie. I tak dalej. Po polsku stosujemy zasady indukcji matematycznej. Czyli jak ja mam złożenie dowolnie wielu kopii konkretnego fa to to też jest w fie.
Niech kie coś się nazywa F do K. No to ja bym chciał przypomnieć, że jest taki taki ogólny fakt dotyczący permutacji, że każda permutacja ma jakiś rząd. To znaczy w ogóle dla każdego faie, niekoniecznie w fie, f jakieś potęgi jest równe identyczność. Tak, do jakiejś nieegłupiej potęgi naturalnej dodatni, do zerowej to z definicji jest identycznością.
Tak. I to jest z ogólnej teorii. I głupia odpowiedź na pytanie, skąd się bierze takie Q jest taka, że patrzymy na kolejne potęgi FA, mówimy, że kiedyś się powtarzają. Y, mądra odpowiedź jest taka, że m na przykład to jest iloczyn z długości cyklu po rozkładzie f na cykle. Kto inny powie, że ta pierwsza odpowiedź była mądra, ta druga jest głupia, bo pierwsza jest pierwsza jest taka w białych rękawiczkach. Tu coś trzeba policzyć, ale to kwestia gustu. M.
No to ja twierdzę, że f-1 to jest f-1. Po pierwsze f do teraz jak już zakładamy, że okej, to jest f- pizzej, tak? Bo f złożone z fq jest to jest fq, czyli identyczność. To w zasadzie wygraliśmy, tak? dla fa, który jest w naszym śmiesznym zbiorze, a f do min to jest f do q- pze, więc ona należy do naszego śpiesznego zbioru, bo on jest zamknięty na podnoszenie permutacji do potęgi, co dowodzi 2.
No i my tego, że to jest pod grupą doliśmy nie po to, żeby korzystać z jakichś mądrych twierdzeń podgrupach i też niezupełnie dla fanów. Jak my tego potrzebowaliśmy, żeby zobaczyć jak cały zbiór F zachowuje się kiedy kiedy składamy go z kiedy wykonujemy działanie. Albo patrzymy na odwrotność albo składamy go z jakimś jego elementem. No i to jest drugie stwierdzenie, które jest jeszcze prostsze, a przekształcenie, jak się nazwiemy przekształcenie odwrotność.
Po prostu nazwiemy tak. C do fa jest biekcją. Tak. To jest no brainer. przekształcenie składania teraz dla ustalonego G. To ja mam dwa przekształcenia. Mam przekształcenie składania zg lewej strony i przekształcenie składania zgwej strony. Tak. domnażanie z prawej strony to jest po prostu FG.
A domnażanie z lewej strony to jest po prostu GF. Jak wiemy, że ono jest dobrze określone. Y w którymś momencie przestałem pisać kółeczka na mnożenie. domyślnie mnożenie w w SN to to złożenie permutacji. No i tutaj dowód to jest jeszcze bardziej no brainer. Branie permutacji odwrotnej. No przekonaliśmy się już, że F jest zamknięty na działanie brania permutacji odwrotnej, które jest w SNE.
To w ogóle jest inwolucją. Jak zastosuję odwrotność dwa razy, to wracam do tego samego miejsca. Czyli możemy zapisać taką piękną równość, że to przekształcenie do minus pierw jest równe tym przekształceniu. Domnażanie G to przekształcenie odwrotne do tego, to jest domnażanie g-1. Jak gło w fie to i g-1 jest w fie. domnażanie fa z lewej strony to chciałem napisać g to odwrotność tego to jest domnażanie jed pierwszy już po prostu to jest cała mądrość zawarta w tych założeniach o o fch że jak weźmiemy całą grupkę fów domnożymy jednego z nich to mamy te same F. Być może jakoś przeszafowała.
Dobra, teraz przyjrzyjmy się przyjrzyjmy się tej tej funkcji z od I. Ja bym chciał się z nią obchodzić trochę inaczej niż w treści zadania. W treści zadania ona jest ograniczona do mniejszego od j. Ja bym chciał ją zdefiniować szerzej. Ja bym w ogóle powiedział, że niech dla i różnego od jem, że inw funkcja f czy permutacja f i zbiór i j to będzie dla mnie znak takiego napisu f j- f i przez j- i f są permutacjami.
W związku z tym jak i jest różne od j po pierwsze mnoik się kompiluje. Po drugie licznik jest różny od zera. Więc funkcja signum nam zwróci coś co jest jedynką albo minus1. No i zwróćmy uwagę na dwie rzeczy. To jest poprawnie zrobiona definicja, bo owszem argumentem jest zbiór, ale tu jest symetria. Jak słapnę i j, to tu będę miał minus i tu będę miał minus. Więc jak zbiór zamiast reprezentować go jako j zrezentuje jako j dostaję ten sam napis. Więc to jest faktycznie funkcja od zbioru, a nie od pary uporządkowania. Co jeszcze chcemy wiedzieć?
To jest -1 do potęgi wartość logiczna. Wartość logiczna tego, że f zmienia porządek. Znaczy, że f od mniejszej z liczb jęsze niż f od większej z liczb. wygląda jak to co jest w zadaniu. Jaka motywacja za tym stoi? ogólnie taka, że [parsknięcie] bardzo chcemy korzystać z tego, że możemy tak przearanżowywać zbiór f i my chcemy stosować fy z tego zadania do tych i jotów, bo jak nie mamy kontroli nad tym, czy fy odwracają kolejność, czy nie, to chcemy móc operować na tych z i j w taki sposób, żeby by nie przejmować się kolejnością j na wejściu.
Więc chcieliśmy zrobić taką definicję, która mówi tak naprawdę o tym jak f odwraca kolejność, a nie nie czy f dla konkretnych i jó miały konkretne posortowanie ją odwróciło czy nie. To ja bym chciał doć jeszcze stwierdzenie. ten znak inwersji permutacji f na jakim zbiorze jad z sna i j który jest pod zbiorem od 1 do n który ma dwa elementy przy takich założeniach to a i tu jest jeszcze jakiś to ja mogę to wyrezentować przez działanie takiego złożenia na zbiorze j ale jeszcze skorygowane o działanie G na czyli chłopski rozum mówi tyle że tu Tu
Jest pytanie, czy G odwraca J, a potem czy F odwraca kolejność jów, ale nie takie bezpośrednio F, tylko f złożone z K minus pierwzy, czyli tak jakbym się cofnął tym G i jeszcze wrócił do Fa, czyli tak jak poszedł od J do G, cofnął się i poszedł do FA. Czyli tak jakby tutaj to jest chłopski rozum. Dowód jest niewiele bardziej skomplikowany. To jest jedna linijka. Można rozważać przypadki. Można napisać, że prawa strona to jest znak wyrażenia f złożone z g-j.
A to zacznijmy od tego, że niech ten zbiór J to będzie jakieś J obojętnej kolejności f(g) do- P1 od G j fg do min od G i taki raz różnicowy razy taki raz różnicowy Nie jest dla nas tajemnicą, że znak A raz znak B to jest znak A x B. Jak mam dwa plusy albo dwa minusy, wychodzi mi plus. A jak mam plus i minus, wychodzi mi minus.
No to ja mogę po pierwsze wrzucić to jedno signum, pomnożyć to z tym pamięci, skrócić tego z tym, tu złożyć G z G do min pierwszej i dostać f j- f i, czyli dokładnie znak inwersji fa na na zbiorze j. Co on ma prosi? Co jeszcze potrzebujemy wiedzieć? Potrzebujemy jeszcze coś wiedzieć o rozkładach prawdopodobieństwa. Tu tak naprawdę tu mamy napisane, że jak ja zalosuję jednostajnie, tak z prawdopodobem 1 przez duże n element dużego fa i go odwrócę, ja powiem, że ten wynik to jest zalosowany jednostajnie, to nikt nie zauważy różnicy.
To napiszemy to w pomyczny sposób. Tak. Niech f będzie będzie zmienna losowo rozkładzie jednostajnym na f. Wtedy f do min pizzej ma taki sam rozkład. Tak. No i to jest selfid.
Rozkład jednostajny to jest zliczanie rzeczy. Jakbym bardzo chciał być pompatyczny, to bym napisał, że prawdopodobieństwo, że F do min trafi do jakiegoś podzbioru A. To jest podzbiór FA. To jest to samo co prawdopodobieństwo, że f trafi do zbioru permutacji postaci a do min pierwzej, gdzie a należy do a. Tak, to wszystko siedzi w fie, więc to jest liczba elementów tego czegoś przez liczbę elementów fa.
Ona się chyba nazywała n. Biekcjazy podnieszenie doc pierwsze jest biekcją na fie, więc to jest liczność a przez liczność fa, czyli prawdopodobieństwo, że samo f wpadnie do, czyli f do mini sam rozkład jak f. To było oczywiste, z grubsze, wtedy to ma taki sam rozkład. A to jeszcze tu zrobimy F złożone z G.
F jest zmien losową, a G należy do F ustalon. Dla F złożone z G, G złożone z F. Dowód jest dokładnie taki sam. To była biekcja na fie, to była obiekcja na fie i to była biekcja na fie. I jeszcze jedna rzecz chcemy wiedzieć. Teraz będziemy mieć losowy zbiór. To ma rozkład jednostajny na zbiorze wszystkich dwentowych podzbiorów.
Oznaczymy go przez symbol Newtona. Zbiór nad dwa. Łatwo się domyślić, że jest dokładnie jedna rzecz, którą to może oznaczać, że to jest rodzina dwudometrowych pozbiorów, której liczność jest akurat n n pod tak oraz f nie musi być fanie ustaw wtedy od J ma ten sam rozkład co J.
Tak. No i dowód jest podobny no brainerem. Prawdopodobieństwo, że f to jest jakiś konkretny zbiór K jest równe prawdopodobieństwu, że J do piz JK. Ale zaraz J ma rozkład jednostajny. Po prostu to jest losowanie w najbardziej chamski możliwy sposób. jednego z n po 2 podzbiorów, to tu jest 1/ n, czyli prawdopodobieństwo, że to j trafiło akurat w zbiórkę. Tak. I tak jak tu było dla każdego a, które jest pod zbiorem F.
Tak samo tu jest dla każdego K, które jest pod zbiorem rodziny dwuelementowych podzbiorów zbioru od 1 dobrze. Czy to są wszystkie nudne oczywistości, których potrzebujemy? Myślę, że tak. Dlaczego to wszystko robiliśmy? Grupowy wbor zadania jest oczywisty. Proabilistyczny jest trochę mniej oczywisty. Gdzie tu widać prawdopodobieństwo?
No więc ja bym zaczął od tego, żeby, bo w treści zadania mamy te z i j tylko dla mniejszego od j. Tak. A ja mogę spokojnie pomnożyć to przez 2. Ja mogę zdefiniować z tak że z od zbioru i j to będzie z treści zadania od dwóch argumentów. minimum tego zbioru i maksimum tego zbioru dla i różnych od j.
Nasze zadanie przez pomnożenie stronami razy 2 tej równości, czyli przez dopuszczenie j więks od i jest równoważne z tym, że tu mamy n/ 2 razy suma po wszystkich dwuelementowych podzbiorach. Tu jest z od J. Miałaby być równa sumie po wszystkich dwometrowych podzbiorach z od J do kwadratu. To ja bym chciał zauważyć, co następuje. Z od J ono jest naturalnie w jednostkach n.
Dlaczego? No bo to jest suma po fach w fie z wartość logiczne zdania. M. wartość logiczne zdania f robi inwersję porządku na zbiorze j. Czyli to jest wartość logiczne zdania tego, że nasze in w fj jest równe akurat -1. Ale tu zobaczcie, że to jest dokładnie tak samo co gdybym tu odfaktoryzował to ile jest składników, bo f miało liczność duże n i tu wziął wartość oczekiwaną z losowym fem.
Żeby odróżnić losowanie f od losowania j to napiszemy tak. To strasznie pobatyczny napis. Ale on mówi dokładnie tyle, że sumujemy po możliwych fach i dzielimy przez ich liczby. Tylko po prostu księgowość na tym napisie jest sprawniejsza. Tu jest indykator wartość logiczna napisu f j f j rów-1. Więc skoro w naturalny sposób z jest w jednostkach n razy wartość oczekiwania jakieś naturalnej zeroj jednowej zmiennej losowej, tu jest n, tu jest pierwsze potęg z i to jest druga, to aż się prosi, żeby to podzielić przez ten kwadrat, aż rozpoznawanie nacisków w długopisie oszalało.
Tak. Jak ja to podzielę przez ten kwadrat, dostanę tutaj 1/2, tutaj sumę po jtach, tutaj z od j podzielony przez n, a tu sumę po jtach z od j tu w środku podzielone przez n do kwadratu. A teraz jeszcze jak ja to podzielę przez liczbę wszystkich możliwych i jotów, czyli przez n po 2, to tak jakbym tu miał wartość oczekiwaną ze względu na losowego j.
Tu jest z od j przez n i tu jest wartość oczekiwania ze względu losowego j z od j przez n i to do kwadratu. To się z tym nie zlało. Tu mamy na zewnątrz losowanie po jie. Tu mamy z od j/ n. Czyli tu mamy wartość oczekiwaną ze względu na losowego fa.
Indykator zdarzenia, że f zamieni nam kolejność na j. Pytają nas czy to jest równe wartość oczekiwana ze względu na losowe j z i teraz całe to do kwadratu. Jeśli w wyniku podzielenia przez jakieś rzeczy zadanie się wyraża także tu w tym napisie już nie ma nów. tu w ogóle jako jako czynnik nie występuje nie występują liczności zbiorów, czyli miary tych miary liczące tych światów, w których to się dzieje. Jeśli to się poskracało i to się wszystko wyraża bez bez jednostek w języku wartości oczekiwanych, to można się spodziewać, że to jest naturalny sposób sformułowania tego problemu.
To teraz będziemy liczyć. To jest to jest na razie nasz wróg. Ja bym chciał zauważyć, że indykator zdarzenia ten ktoś jest jedynka albo minus1, no to ja mogę napisać, że to jest 1 minus ten ktoś przez 2 plus. Jeśli on był -1, to mam 1-1/ 2, czyli 1. Jeśli on nie był -1, to był 1. Tu mam 0, tu mam 1- 1, mam 0.
Ogólnie dla x, który jest jedynk albo -1, wartość logiczna zdania x = -1 to jest dokładnie 1- x/ 2. Ten dźwięk to jest kot atakujący drzwi. Patrzcie, oto kod. Pokaż się kot. kocie w pełzanie między szybę i biurko może się źle skończyć to napiszmy ten napis EF z tego indykatora z tym prawem rachunkowym Dobra,
Jest kod w naturalnym środowisku. Tymczasem coś mieliśmy policzyć. A y ten EF to jest pompatyczny napis. Tam jest wartość oczekiwana, ale to jest po prostu sumowanie po fach z normalizacją przez liczbę fów. To jest to samo co wartość oczekiwana z po fie z 1/2 x 1-zna funkcja inf, czyli 1/2 wartość oczekiwana jest liniowa. Jak to suma?
Wartość oczekiwana po fie jest z jedynki minus wartość oczekiwana po f jest invw 1/2 x 1- z inw taki To tutaj mamy do policzenia 1/2 losujemy j 1/2 1 minus Losujemy fa, patrzyli na znak inwersji i pytają nas, czy to jest to samo, co gdybyśmy kocie jeszcze mruczy.
Co gdybyśmy wylosowali jota i tu całe towarzystwo wzięli do kwadratu? Fakt, że skraca nam się 1/2 w liczbie sztuk D, to jest dość silna silna przesłanka, że coś tam wyszło dobrze. Jeden, drugi się skracają. Tu, tu zostaje 1 minus średnia po jednym i po drugim. A tu zostaje coś trochę gorszego.
Tu zostaje 1- do kwadratu, czyli 1- 2 razy ta średnia po fie plus średnia po f jest inf a do kwadratu. I znowu się mnóstwo rzeczy skraca. Skraca się jedynka. Ten ktoś się przenosi tu. Tu jest w lwie sztuk minus2. To jest min1. Kocie naprawdę kod się przemieścił.
Tymczasem byliśmy gdzieś tu. To się skraca. To się przenosi na drugą stronę. Zostaje nam jedna sztuka wartość oczekiwana po jednym i drugim. A tu jest wartość oczekiwana na zewnątrz pocie. W środku mamy wartość do kwadratu. No i tu znowu to ja ja udaję, że że to jest że to jest mądre. To nie jest mądre. To jest po prostu sumowanie po jednym indeksie fest normalizacyjną.
Co się dzieje kiedy sumujemy po fie jakiś napis i powiedzmy jakieś a od fnosimy to do kwadratu? To jest to samo co gdybyśmy mieli sumę po dwóch indeksach. które biegają w tym samym zbiorze. Napis od F razy napis od G. Jak tutaj dorobię normalizację 1 n, to tu mam normalizację 1/ n kwadrat. Tak? Czyli tu tak jakbym losował fa ze zbioru duże F, a tu jakbym losował parę FG z wielczynu kartezjańskiego duży Faz duży F. Pamiętamy, że to chcemy udowodnić.
Tu ja twierdzę, że jest napisane EJ e ze względu na niezależnie losowane f i g in od fj inf od [parsknięcie] g. I teraz przechodzi nam z pomocą to to prawo, jak się zachowują te znaki, znaki inwersji przy składaniu permutacji. To jest to, co zapisaliśmy gdzieś. Gdzie zapisaliśmy? O, tu. Nawet zapisaliśmy to już w formie, która jest do natychmiastowego zastosowania.
To wszystko są znaki. To są plus minus jedynki. Więc jak pomnożę przez tego, to tu mam infj raz inf GJ i po prawej stronie zostaje mi ten, się nie pomylić w przepisywaniu. Zrobię progamer mów. To jest równe ej EFG z takiego napisu. No i co się ukazuje naszym oczom? Mamy tak jakby trzy sumowania i napis, w którym którego tylko części zależą od tych indeksów.
F się pojawia tylko raz, więc napiszmy to tak, że tu jest EG i tu jest EF. Wszystko co się dzieje z femust j i g to jest to, że jest ustalony g do pierwszej i mnożymy go ze z losowym fem. F przebiega cały zbiór duże f jednostajnie. To przy ustalonym G FG do pi dokładnie tak samo przebiega zbiór fedostajnie. Ja twierdzę, że to jest EJ, eg e in f od wait coś tu jest coś tu jest absurdalnie napisane.
Y, tu się wkradł absurdalny napis od J. Tego od J tutaj nigdy nie było. Takie rzeczy się dzieją, jak się pisze jedno, myśli drugie i mówi trzecie, nie polecam. O i teraz wszystko gra i buczy. FG do- pi to jest po prostu f był zmienna jednostajna na fie to 1 min pierwszej też czyli tam po prostu f g j teraz teraz co wylosujemy najpierw teraz najpierw wylosujemy j tu zostawiamy e egf mamy j tu mamy w F G.
Tak. I teraz mówimy, że przy ustalonych G i FJ J z losowym jem to jest to samo co J. Bo powiedzieliśmy, że kiedy J ma rozkład jednostajny, to deterministyczny G przyłożony do tego ja dalej ma rozkład jednostajny. Takie coś. Ten napis w ogóle już nie zależy od G. Od G to jest stałe, więc zostawiamy e od względem F i J FJ. Ojej, wyszło nam. Sumowanie jest przemienne. Nieważne czy bierzemy najpierw EJ, potem EF, czy EF, potem Ej.
JF to jest 1 przez takie coś. Nie jotów, tylko ten i na odwrót tak samo. Już policzyliśmy.