Zadanie 11 z I etapu 76. Olimpiady Matematycznej — rozwiązanie
Olimpiada Matematyczna⏱ 47 min
Rozwiązanie zadania 11 z I etapu 76. Olimpiady Matematycznej – „prezentu od probabilistów”. Najpierw trzy narzędzia, które warto znać, potem pełne rozwiązanie z błądzeniem losowym w tle.
W tym nagraniu
Symbole wielomianowe (multinomialne) jako uogólnienie dwumianu Newtona
Zliczanie przez przeciwobrazy i „filtry” na współczynniki wielomianu
Średnie i nierówności między nimi
Niezależne zmienne ±1 – rzuty monetą i błądzenie losowe
Rozwiązanie zadania 11 z I etapu 76. Olimpiady Matematycznej (2024/2025), nazwanego „prezentem od probabilistów”. Zanim pojawi się samo rozwiązanie, nagranie przypomina trzy narzędzia, które warto mieć w głowie na olimpiadzie.
Pierwsze to symbole wielomianowe (multinomialne), uogólnienie dwumianu Newtona: współczynnik przy x₁^k₁·…·xₘ^kₘ w rozwinięciu (x₁ + … + xₘ)ⁿ to n!/(k₁!·…·kₘ!). Drugie to „filtr podzielności” — sposób wyłuskania z wielomianu sumy tylko tych współczynników, których wykładniki spełniają warunek podzielności. Trzecie to nierówności między średnimi.
W samym rozwiązaniu zliczanie zamienia się w rachunek prawdopodobieństwa: niezależne zmienne przyjmujące wartości ±1 to rzuty monetą, a ich sumy — błądzenie losowe. Nagranie jest dobrym materiałem dla uczniów przygotowujących się do Olimpiady, którzy chcą zobaczyć, jak kombinatoryka łączy się z probabilistyką.
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. (5076 słów)
W związku z upłynięciem terminu trzeciej serii pierwszego etapu olimpiady matematycznej, nadszedł czas na rozpakowanie prezentu od probabilistów, który występuje pod nazwą handlową zadanie 11. Zanim je zrobimy, to chciałbym opowiedzieć o trzech rzeczach, które które się powinno wiedzieć do tego. Jedna to są symbole multinomialowe. Ogólnie nie wiem jak to się po polsku nazywa. Być może po prostu nie ma ustalonej nazwy. Chodzi mi o takie uogólnienia symboli wymianowych, które znamy ze wzoru na a+ b do nte.
Pamiętamy, że były jakieś takie takie sztuczki, że a + b do n tej to była jakaś taka suma n po k a do k tej b do n min k tej. Więc ten napis wygląda dość symetrycznie. Ogólnie no wiadomo, że można zamienić k na n- k. Wtedy to co stanie a i b się zamienią miejscami. Widać te symetrie, które jest po lewej stronie. Widać ją jeszcze bardziej, jak to napiszemy w takiej formie, która jest symetryczna ze względu na k i n- k. To znaczy napiszemy jako sumę po indeksach, które się sumują. Tu n silnia, tu k silnia, tu razy l silnia i tu a do k tej, b tej.
Tak. Teraz widać absolutnie jak na dłoni, że to jest symetryczne. Jak się tego dowodziło? No także się także najpierw się dowodziło twierdzenia, że że NP po k to jest liczba sposobów, na które możemy wybrać albo inaczej, że to coś to jest liczba sposobów, na których możemy zrobić partycję zbioru elementowego na dwa kawałki. Tak, są dwie alternatywne definicje. Jak jedną przyjmiemy za definicję, to druga jest twierdzenie. Jak powiemy, że że n po k liczba podziałów zbioru jakiegokolwiek n elementowego, na przykład 1n na sumę dwóch takich, że pierwszy ma dokładnie k elementów i drugi ma dokładnie n- k elementów.
Jak to jest definicja? No to ten wzór to jest twierdzenie nieprzesadnie trudne. Dlaczego to jest równe n silnia przez k silnia razy n- k silnia? No na przykład to znaczy ad algorytm argument jest taki, że że się pisze przez rachunki na silniach. O że to jest takie coś n- K, tak, żeby było k czynników, czyli n- K + 1 przez K silnia. No i co się mówi? Mówi się, że taki podział to jest to jest najpierw najpierw wybranie zbioru zbioru A, a potem B jest zdeterminowany. W związku z tym musimy wybrać k elementowy podzbiór.
No to jak go wybieramy? Wybieramy pierwszy element na n sposobów. Drugi zostały n- 1, trzeci n- 2 i tak dalej. Tylko, że tak to wybraliśmy ciągi. A nas pytali o podzbiory, czyli nas pytali o strukturę danych, która zapomina kolejność i z tego jest dzielenie przezka silnia. Jakbyśmy chcieli być bardziej fensy, to byśmy powiedzieli na przykład, że o jakbyśmy powiedzieli? powiedzielibyśmy, że bierzemy permutację zbioru, zbioru elementowego i z nich robimy funkcje właśnie takie podziały, podziały n na kn- k.
No bardzo prostą taką, że permutacja sigma przejdzie na sigma od 1 sigma od k. To jest jeden zbiór, a drugi to jest reszta. Sigma od k + 1 bla bla bla sigma od n. No i to jest taki formalny sposób powiedzenia tego, co ja tutaj zamachałem rękami, bo bo teraz co? To oczywiście jest funkcja na każdy każde dwa podzbiory da się napisać jako obraz takiej permutacji, bo wylistuj elementy i powiem, że to jest permutacja. Tylko, że jak ja tutaj mam jakiś podział i jakieś dwa zbiory AB, no to przeciwobraz tego punktu w tej funkcji to są permutacje takie, że wartości na pierwszych k elementach to są jakoś tam ustawione a, a na tych to są jakoś tam ustawione b.
No to takich permutacji, że które idą ze zbioru 1k, znaczy takich biekcji, które idę ze zbioru 1k w a jest dokładnie k silnia. Takich biekcji, które idą ze zbioru k + 1 w b jest dokładnie n- k silnia. Tak więc jak to jest nazwijmy to powiedzmy fika, to możemy powiedzieć, że przeciwobraz przeciwobraz w tym <un od czegoś takiego ma dokładnie tyle elementów. W związku z tym dziedzina, co jest w związku z tym dziedzina to jest to jest co?
To jest to, o co nas pytają, czyli moc tego zbioru razy k silnia razy n min k silnia. Z tego się już nie trzeba tłumaczyć, że to jest n silnia. Dlaczego przeninżenierowałem dowód faktu, który znamy ze szkoły? dlatego, żeby się go dobrze uogólniało. Teraz chcemy zrobić takie coś. Jak ten wzór można uogólniać na to znaczy dobrze, to jest jedno uogólnienie wzoru na a + b do kwadratu na n to potęgę. Znamy też wzór na sumę n składników do do kwadratu. Więc w pewnym sensie to jest to takie uogólnienie w dwie strony. Tu mamy dowolnie dużo składników i tu mamy dowolnie dużą potęgę.
Dobra, to jest nasz nasza pierwsza rzecz do opowiedzenia. Teraz to coś to zdefiniujemy dokładnie tak samo. To jest liczba podziałów zbioru n elementowego na ponumerowane zbiory. takie, że takie, że a1 ma k1 elementów, bla bla bla, as ma ks elementów. W szczególności to pojęcie ma sens tylko wtedy, kiedy kiedy k się sumują do n.
Tak? Wcześniej prosto było myśleć o podział na dwa rozłączne zbiory. Tutaj jak to jest podział na s rozłącznych zbiorów, no to to jest na poziomie czystego abstrakt sensu to samo co liczba funkcji. funkcji o zbioru 1 w 1s takich że powiedzmy niech to będą funkcje f takich że przeciwobraz każdego każdego z tych indeksów ma tyle elementów co każą co każą k jeszcze inaczej to jest liczba sposobu pokolorowania liczb od 1 do n s kolora Tak, bo wtedy po prostu ta funkcja to jest przyporządkowuje liczbę kolor.
Jak się tego dowodzi? albo takim argumentem jak tutaj. To znaczy mówimy, że bierzemy taką wielką funkcję fi, która idzie z permutacji w to, co nas pytają, jak podziały z takimi licznościami i mówimy, że tak samo jak wcześniej fi od permutacji to jest pierwszy zbiór, to będzie sigma od, no to będzie pierwszy k1 danych. sigmy, potem będzie pierwszych, potem będzie następnych następnych K2 danych z sigmy. O i tak dalej.
No i nietrudno się przekonać, że przeciwobraz od cokolwiek, dowolny element przeciwdziedziny. To jest dokładnie tyle permutacji, że liczby od 1 do k idą w pierwszy zbiór z tego czegoś. Czyli ich jest K1 silnia, następnych jest K2 silnia i tak dalej. I takim samym rachunkiem to jest kilka putacji podzielona przez moc każ przez wspólną liczność wszystkich przeciwobrazów, czyli czyli to co mieliśmy udowodnić, że że to jest gzie mieliśmy udowodnić równa się nie napisałem tego jawnie, ale tak który ze mną bywa.
Stąd symbol multinomialowy to jest n silnia przez iloczyn sil. Tak. I stąd widać, że to jest naturalne uogólnienie. Naturalne uogólnienie tego symbolu dwumionowego, który znamy. No i wzór dwumionowy się ogólnie dokładnie tak samo. Robi się opowieść o wymnażeniu nawiasów. Jak zrobię taką sumę do ntej, wcześniej wymnażałem n nawiasów. Z każdego brałem jeden, z każdego czynnika brałem jeden z dwóch składników. To miałem 2 do n jednomianów. Każdy miał taki stopień jak ta potęga tutaj. To będzie dokładnie tak samo. To będzie s do n jednomianów.
Jedne jednomiany, które mają prawo się pojawić przy tak wymnażaniu, to będą te, które są jednorodne stopnia. yym jednorodne stopnia n, czyli to są takie napisy po wszystkich ciągach k, które się sumują do do. No i dokładnie taki spotkamy tyle razy, ile razy się zdarzyła taka sytuacja, że mieliśmy takie przyporządkowanie numerowi czynnika numeru a, który bierzemy z tego czynnika, że trafiliśmy w jedynkę k1 razy, w dwójkę k2 razy i tak dalej. Czyli dokładnie dokładnie to, co policzyliśmy. No. No i to jest taka taka tam kursowa wiedza, która czasem się pojawia. Ten wzór na a + b + c do kwadratu to jest trywialna konsekwencja tego, jak się to do trzeciej, to już prościej chyba nawet pewnie to stąd niż niż przez takie rozpisywanie.
Tak, tu są takie ciągi, które są 3 + 0 + 0, ciągi postaci 210, czyli takie a kw b i wszyscy koledzy ab k + b² c. Tak, tak, żeby to było sześć składników. Każdy z nich się pojawi ile? Trzy silnia przez dwa silnia, jeden silnia, zero silnia, czyli 6/ 2, czyli trzy razy. No tak. No i oprócz tego trójkę można napisać też, znaczy tylko jako 300, 2 albo 1 + 1 + 1 i 1 + 1 + 1 to jest po prostu ABC. No i to będzie w liczbie sztuk 6, bo to jest 3 silnia przez 3 jedynki.
Dobra, to wiemy jedną rzecz. Druga rzecz, którą, którą powinniśmy wiedzieć, to jest filtr podzielności. To jest multinomial symbol albo multinomial coefficient jak to woli nazywać filtrz podzielności. No więc w tym zadaniu się używa tego trijalnego, tego, który tak naprawdę jest tego samego, który się pojawia, jak się rozkłada funkcję na parzystą, nieparzystą. To znaczy ja będę używał takiego znaczka, który jest trochę nieformalny, to znaczy pogrubiona jedynka.
I tu napiszę jakieś zdanie logiczne, powiedzmy P, to ja powiem, że to jest jeden, gdy gdy p gdy nieprawda, że P. Tak, normalnie to jest nazwa własna dla jedynka jedynka zbiór od jakiegoś czegoś to wtedy się mówi, że że to jest jedynka, gdy x należy do a i 0, gdy x nie należy do a. Natomiast jak się napisze jedynkę jedynkę i i forma zdaniowa to jest grubsze to samo. M to ja bym chciał napisać indykator tego, że 2 dzieli jakąś liczbę.
No to jest dość proste. No chcę mieć taką funkcję, że to jest jeden gdy k parzyste i zero, gdy k nie parzyste kocie. Nie po klawiaturze. Nie tym razem. Jaki grzeczny kot. Y. W każdym razie to się pisze z marszu. Widać nieuzbrojonym okiem, że działa. Ogólnie taki filtr się daje zrobić dla każdego n, gdzie zrobić to znaczy opisać wzorem, tak? Bo to jest jakiś tam wzór, to jest jakaś funkcja na na liczbach całkowitych.
Ogólnie jak ja chcę napisać filtr tego, że n dzieli k to nie to dla dwójki to się mogłem obyć w ten sposób. Ogólnie to ja muszę zatrudnić liczby zespolone. To jest 1 sumy m powiedzmy j = 0 do n - 1. I tu biorę n pierwiastek z jedności do potęgi j x k, gdzie omega n cosinus 2 pi/ n + i sinus 2 pi/ n. W naszej komfortowej sytuacji, w której n jest równe 2, to po prostu jest równe -1. Na przykład omega4 jest równe i tego się używa. I yyy w tym tak naprawdę chodzi o to, że to są kolejne wierzchołki wielokąta foremnego, takiego n kąta foremnego wpisanego w w okrąg ośrodku zero i promieniu 1. Tu jest 1, tu jest omega n, tu jest omega n kwadrat i tak dalej.
I to jest taki z grubsza folklor, którego się prosto dowodzi, że że jak że jak ja biorę co pierwszy wierzchołek nąfernego wpisanego w taki okrąg, to środek ciężkości jest dokładnie w zerze. Jak biorę co co któryś, na przykład jak to jest 17, biorę co piąty, to mam taką strasznie gwiazdistą figurę i tak środek jest w zerze. Jak nawet mam sześciokąt, biorę co trzeci, to jest ten i ten. Jak biorę co drugi, to jest tak, też jest zero. Jedyny sposób, żeby nie było zero, jest taki, żeby przez cały czas stać w tym wierzchołku. I to jest dokładnie wtedy, kiedy skaczemy tylko co n. I to jest tutaj napisane, że jeśli to k, o które skaczemy jest podzielne przez n, to to jest 1, a w przeciwnym wypadku jest zer. Nie trzeba tego wiedzieć, żeby zrobić zadanie, ale warto. Warto dlatego, że spójrzcie tutaj napisaliśmy indykator podzielności jako sumę ciągów geometrycznych ze współczynnikiem. Tak, jeden to jest też ciąg geometryczny, to jest 1 do k. Tutaj jako funkcja k, no to jest jakaś liczba omega omega n do potęgi j i jeszcze do potęgi k, więc to jest średnie arytmetyczne jakichś ciągły geometrycznych.
To jest strasznie przydatne wbrew pozorom, a może i zgodnie. No to jest filtr podzielności. No to jak ja chcę zrobić filtr z podzielności dla więcej liczb, na przykład chcę napisać indykator stwierdzenia, że 2 dzieli k1, 2 dzieli k i tak dalej, 2 dzieli ks. No to to jest wartość logiczna koniunkcji zdań. To to dokładnie jedynka i zero są tak zrobione, żeby to był iloczyn, taki zwykły chamski iloczyn w dziedzinie w rzeczywistych, nawet całkowitych. To jest dokładnie tak zrobione, żeby żeby indykator zdania P razy indykator zdania Q indykator zdania P koniunkcja Q.
No czyli to jest iloczyn. Dob. Najpierw napiszmy, najpierw napiszmy tak, że to jest 1 +-1 do k1/ 2 x raz 1 plus-1 do ks. A teraz jak wymnażamy takie wielkie mnóstwo nawiasów, to czy ja powinien był od tego zacząć? Teoretycznie tak, ale to jak wymnażamy mnóstwo nawiasów, tak jak mówiliśmy, jak to był ten sam nawias a plus b, to wiedzieliśmy, że bierzemy te dwa do ntej iloczynów. Tu tak samo, tylko po prostu nie jest ten sam nawias 2 do s tej suma.
I teraz suma z czego ja to chcę napisać w przeninierowany sposób, tak? Czyli ja mógłbym napisać taką sumę. Tu bierzemy bity. Jeden bit, drugi bit i tak dalej. BS01. Umawiamy się, że w tej sumie pojawi się co następuje 1, gdy A to będą takie iloczyny, że ja biorę coś stąd, coś stąd i tak dalej. 1, gdy B1 jest równy 0 i -1 do k1, gdy B1 jest równe 1. No i już powoli widać konspirację.
Klik, klik, klik. I tak samo dla wszystkich tych to jest do KS. No to ja to mogę napisać w jeszcze bardziej przeinżenerowanej formie. Tak wiem. Trudno uwierzyć, że można jeszcze bardziej nagmatwać najprostszą możliwą rzecz tylko po to, żeby były ciągi geometryczne. M. No bo spójrzcie, tu jak B1 jest równe 1, to temu się nic nie dzieje. To ja tutaj mogę domnożyć B1.
A tutaj jak B1 jest równe 0, to mogę hyrze napisać k1 x B1, bo to i tak jest 0, to będzie 1. Tutaj dokładnie tak samo. Jak BS jest 0, to jest KS x BS, a jak BS jest 1, to jest KS R BS. To teraz możemy to triumfalnie napisać jako 1 przez 2 do S. Suma B1 bla bla bla BS 01 M -1 do K1B1 plus plus K SBS. Tak, dodam, doda nam się wykładnik, tutaj pomnożyliśmy.
No i pięknie. Jest najbardziej dziwny sposób napisania, stwierdzenia, że te wszystkie liczby są parzyste. Można o tym myśleć w taki sposób. Jak wszystkie są parzyste, to gołym okiem widać, że tu jest jedynka. Tu jest 2 do n składników przez 2 do s te składników. Tu jest przez 2 do s, więc wyjdzie 1. A jak chociaż jedna jest nieparzysta, to ona wprowadza asymetrię. Asymetria działa. Działa tutaj tak, że spójrzcie k1, znaczy k1 jest równe 0 albo 1 tak naprawdę, bo m bo to jest w wykładniku minus1, więc liczy się tylko modelu 2. Jak k1 jest parzyste, to tego nie ma. A jak k jest nieparzyste, to słapnięcie B1 na z jedynki na zero to minusuje to. Czyli zawsze jak mam jakieś od k do ks to tu mam jakiś iloczyn razy -1 do k1 b1.
Jak ja zrobię słab, który zamienia B1 na 1- B1 i ogólnie na współrzędnej BJ na 1- BJ, to ten słab mi już powoduje, że ta suma jest zerem, bo zamienie kolejności składników powoduje wystąpienie minusa. W każdym razie jest sobie taki napis. Tak, mogliśmy pewnie. Dobrze, nieważne. Ostatnia rzecz, którą trzeba wiedzieć, to nierówność średnich średnich w szkole i on się pisze w jakiejś takiej postaci, nie? W szkole to się w ogóle zaczyna od tego, że m że suma xk² k = 1 do n i z tego się bierze pierwiastek, że jest większe równe niż bla bla bla. To już napiszmy je też jako jako sigma.
O, to jest suma xk przez n. Na przykład dla xów nieujemnych. Dobrze. No więc to się daje pousprawniać. To się daje pouprawniać i pouogólniać. Akurat to jest nierówność między średnią arytmetyczną i kwadratową. Tu mamy ten, tak? To jest do pierwszej potęgi tak jakby pierwiastek pierwszego stopnia. Ogólnie ta nierówność jest prawdziwa też dla xów ujemnych, tylko po prostu to, że mamy wykładniki 1 i 2 to powoduje, że że wolno nam pisać wolno nam pisać potęgi o takich wykładnikach.
Ponadto jakby jakby to napisać tak głupio d pioska trzeciego stopnia i pierkę pierwszego stopnia to też by trzeba uważać, bo bo wtedy to by działo dla xów i dla minus xów. i wtedy nie równość by się zrobiła w drugą stronę. To to generalnie tak nie działa. A więc tu się stawia moduły po prostu. Jak jest prawdziwa ta nierówność z modułami? Bo jak jest prawdziwa dla nieujemnych, to i można tu postawić moduły, zastosować to do modułów i powiedzieć, że jest takie coś. Zmazać to to założenie. O, tu dopisać moduły, bo udajemy, że to liczby zespolone i o jeszcze tu będziemy fensy i napiszemy do potęgi 1/2 i drugiej.
No fajnie. Y, w trakcie przygotowania do olimpiady się dowiadujemy, że m takie coś jest sprziwiowanych wykładników, które są uporządkowane. To znaczy jak ja mogę m jak ja zrobię tak, że tu wezmę P, tu wezmę 1/ P, tu wezmę Q, tu wezmę 1/ q i to jest prawda dla P większego równego Q. Jest też wersja ważona i jest też wersja ciągła. To co warto sobie zdawać sprawę to to, że średnie to są takie wartości oczekiwane.
To znaczy m jak ja mam zmiennę losową x, to jest zmienna losowa taka, że prawdopodobieństwo, że x trafi w xk jest równe 1 n dla k od 1 do n. Świetna zmienna losowa. Jednostannie losuje liczby od 1 do n, a potem wypluwa x o takim numerze. No to itse to reason. że jej wartość oczekiwana po polsku średnia po francusku SP Hes to tak tr story to e się wzięło od tego że to nazywali SP Hons i jeszcze potem przez długo w podręcznikach to się nazywało nadzieją matematyczną to jest ogólnie to jest suma po wszystkich możliwych wartościach które przyjmuje x jeśli jest ich skończenie wiele z wartość razy prawdopodobieństwo, że zmienna trafi w tę wartość.
W naszym wypadku te wartości to są xy od pierwszego do ntego. Prawdopodobństwo trafienia w każdy to jest 1, czyli też ta średnia arytmetyczna. Więc te nasza nierówność jak możemy napisać tutaj po prostu bohaterami są moduły xów do ptej, a tutaj bohaterami są moduły xów do q. Tu jest średnia moduły x do p, tu jest średnia moduły x do k. Brzydko tak mówić, że bierzemy ciąg i go podnosimy do potęgi, bo tak się przyzwyczaiśmy mówić o funkcjach, a zmienne losowe się nie przejmują. Więc nierówność średnich w naszym wypadku brzmi w ten sposób. Ogólnie o tym można robić cały wykład.
Warto sobie zdać sprawę z tego, że jak podstawimy moduł x do qutej równy y i powiemy, że p przez q. Dla ustalenia uwagi niech t będzie większe równe 1. Tak, tak. No to to jest dla dodatnich, znaczy ta konstrukcja jest dodatnich p. Potem się jeszcze przechodzi przez zero. To osobna opowieść. W każdym razie jak się tak podstawi to to się sprowadza do tego, że średnia zmienna losowa funkcja odwrotność tej funkcji większa równa średnia.
To jest szczególny przypadek tak zwanej nierówności jensena. Nierówność po prostu mówi, że jak wezmę funkcję wypłukłą, przyłożę ją tutaj pod średnią, zrobię średnią, potem się cofnę tą funkcją, to wyjdzie mi więcej niż niż zrobimy samą średnią. No natomiast chwilowo tego nie trzeba wiedzieć. Chwilowo trzeba sobie zdawać sprawę z tego, że jak mamy jakikolwiek zbiór, sumujemy po nim wartości czegoś do jakiejś potęgi i potem bierzemy, bierzemy średnio i bierzemy do pierwiastek z tego samego stopnia, to im większa potęga, tym więcej. Czy my wiemy wszystko? Generalnie tak. Mamy tu kota w sałatce z kabli. Po niemiecku kabel salat. Trust story jest takie słowo.
Dobra to wiemy kursowe rzeczy. To teraz zadanie. No więc pierwsze skojarzenie to jest multinomial. No tylko, że to są jakieś dwukrotności. Jak sobie z tym radzimy? A zróbmy podstawienie. Niech duże K to będzie dwa razy małe K. No to to CN, o które nas pytają, to jest suma. Teraz duże K się sumują do 2n. K1 plus+ plus akurat to nazwali tutaj L. To się sumuje do 2N, ale oprócz tego, że sumuje się te 2 n, to jeszcze muszą być parzyste tu 2n silnia i tu są prosto duże K.
KL silnia. Jak już wszystko zapisujemy w terminach dużych K, zróbmy tak, żeby mieć więcej miejsca. Tak, to jeszcze powiedzmy, że niech AJ to będzie alfa J do kwadratu. Wolno nam, bo są dodatnie. Tak. O, to świetnie. To możemy teraz nawet napisać to pod sumą w jednej linijce. Tak. I teraz A1 do K1 to po to nam była ta alfa, żeby zobaczyć alfa 1 do 2k1 po polsku do dużego K1 razy razy alfa L do dużego KL.
Tak jak ten książę Krwawych Elfów w Warcrafcie, chyba też się nazywał KL. W każdym razie tu suma po dopisaniu jakiegoś warunku logicznego to jest nic innego jak pomnożenie przez jeden składnika składników, które spełniają ten warunek logiczny i przez zero tych, które nie spełniają. Tak. Tak. I tu chcemy się pomnożyć przez indykator tego, że 2 dzieli wszystkie k. No to my na niego mamy paragraf. Teraz napiszemy najdłuższą sumę, jaką napisaliśmy w ciągu ostatnich paru dni.
To jest suma po kórych domyślnie wszystkie są naturalne z zerem. Tak, tak jak te wszystkie wszystkie k i n wniane newtone one były od zera. Tak tu jest 2n. Możemy już przestać udawać, że nie wiemy, że to jest symbol multinomialowy. Tu jest alfa 1 do k1 x raz x alfa l do kl. A tu jak znakomicie pamiętamy, tu jest 1/ 2 do liczby indeksów razy suma po wszystkich możliwych ciągach bitów z -1 do B1 plus plus BL KL. prędko zanim nas dojdzie, że to bez sensu.
Mamy dwie wielkie sumy. Twierdzenie mówi, że jak spotykamy w lesie taką podwójną sumę, to ona się zrobi prostsza, jak zamienimy kolejność sumowania. 2 do L to w ogóle jest stałe. To wychodzi przed wszystko. Tu jest suma pociągach bitów. Tak. A w środku będziemy mieć sumę po k. Niestety k są już w każdym z tych trzech czynników, ale to nie szkodzi. Takie coś. Tu jest nasz multinomial. Tu jest. I teraz tak a priori tu mamy alfa 1 do k1 x raz x raz x alfa l do kl -1 do b1 k1 x raz x raz -1 do bl.
No to nie sprawia szczególnego zdziwienia, że teraz teraz przearanżujemy czynniki. Tutaj alfa 1 się lubi z tym. Jak się pomnożą, to wyjdzie -1 do B1 alfa 1 do potęgi K1 razy razy -1 do BL alfa L do potęgi KL. No to wygraliśmy, zwinęliśmy sumę.
Tu tu jest dokładnie wzór multinomialowy. Tak powinienem był w ogóle jak ja zastosowałem to to w tym miejscu to powinien był przeskrollować do do tego momentu, w którym to napisaliśmy o że mamy takie coś które wyszło z takiego czegoś. Tu jest dokładnie nasz nasz wzór multinomialowy. Jest suma po indeksach, które się sumują do tego, co jest na górze z doczynu zmiennych do tych indeksów. To jest 1/ 2 do Lj suma po bitach i tu jest -1 do B1 alfa 1 plus plus -1 do BL alfa L wszystko do potęgi 2N.
Tak. I to było nasze CN. No i wydawać by się mogło, że owszem dostaliśmy inny napis. Dlaczego ten napis jest świetny? Dlatego, że mogę zrobić następującą operację. Ach, zaraz, bo to w ogóle jest taka nierówność. No to jeszcze lepiej. Ja bym teraz chciał powiedzieć, to jest to jest pierwiastek n stopnia, więc ja tu chcę mieć. A okej, dobra. To ja bym napisał to w taki sposób jeszcze.
O, na razie nic nie zrobiłem. Więc powiemy, że to jest 1/ 2 do Lj sumy po bitach z alfy są ustalone to jest jakaś funkcja odbitów do n gdzie nasza funkcja to jest kwadrat Suma -1 do BJ alfa J.
No to jak dla mnie to wygraliśmy. No patrzcie, tych bitów jest tych ciągu bitów jest 2 do nte 2 do Lj. Tak, tu jest L, tu jest 01. Dzielimy przez ich liczbę. Tu jest coś. To, że ja to nazwałem funkcją, to to jest przegloryfikowany ciąg. Funkcja na zbiorze skończonym to ciąg. Ciąg na zbiorze skończonym to funkcja. Cn to jest jak już ustaliliśmy 1/ 2 do lj sumy pociągach bitów f odciągu bitów do ntej. Pytają nas o pierwiastek n tego stopnia z Cn i pierwiastek n plus pierwszego stopnia z Cn + 1.
Warto było to jeszcze napisać, że to jest większe równe zer. No to ta nierówność to jest po prostu pierwiastek n stopnia z 1 2 do lj. Suma pociągach bitów to do potęgi n tej mniejsze równe niż n + 1 n + 1 toż to jest dokładnie nierówność średnich dla średnich rzędu nn plus 1 to jest ta najbardziej szkolna nierówność.
Gzie przez najbardziej szkolne mam na myśli, że tu jest w ogóle 1 przez liczbę tych wszystkich nawet nie ma wagi. To jest tak jakby nierówność między średnią arytmetyczą i kwadratową, tylko zamiast n rów 1 jest n rów n. n rów 1 to jest dokładnie tu jest średnia arytmetyczne a tu jest kwadratowe. Skąd komukolwiek mógł przyjść do góry pomysł na takie zadanie? No więc podstęp, który ja wietrzę jest taki. To jest zmienna losowa. Na to możemy patrzeć jako na ciąglipów. I mówiliśmy sobie, że ten jensen tak naprawdę to jest opa zmiennych losowych. By the way, jak się tam udowodni, że jakieś tam rzeczy się przybliżają przez coś dyskretnego albo albo jeszcze inaczej to zrobi, to to się takie coś tu było dla zmiennych losowych o skończenie w jego wartościach. To jest prawda po prostu dla zmiennych losowych, dla których te napisy mają sens.
Tutaj to jest zmienna losowa. B to jest nasza przestrzeń probabilistyczna. Tak naprawdę jak tam przestrzenia probabilistyczną było od 1 do n tylko, że tutaj naszym n jest 2 do l. A to jest coś dość szczególnego. To są tak zwane zmienne radchera. Tak. Jeśli ja powiążę przestrzeń probabilistyczna, tak to jest zbiór zdarzeń elementarnych i prawdopodobieństwo dla niej to jest skończone, więc to mierzymy każdy zbiór. Jak dla mnie to będzie ten zbiór ciągów bitów do Ltej i miara licząca podzielona przez 2 do L, to wtedy F to jest zmienna losowa.
Po polsku funkcja na przestrzeni probabilistycznej. Te wszystkie funkcje, które biorą b i zwracają -1 do b j, to one biorą wynik któregoś coinflipu i z tego wyniku coinflipu robią plus minus 1 z równymi prawdobieństwami. Więc one są niezależne i nazwijmy je rj. I prawdopodobieństwo rj = 1 jest równe 1/2. I tyleż jest równe prawdopodobieństwo RJ rów -1. To ma swoją nazwę. To się nazywają zmienny Rademera.
No więc i on nie się myśli w ten sposób, że tu jest suma raderów ze współczynnikami. Czyli o tym się myśli w taki sposób. Jak f b to jest f b to jest yyy to jest r1 alfa 1 plus r2 alfa 2 i tak dalej. No to r alfa 1 jak mam oś lirbową startuje z zera. R1 alfa 1. No to ja się decyduję, czy ja pójdę tu, czy tu. No powiedzmy, poszedłem tutaj. Teraz się decyduje o R2 alfa 2. To ja mogę pójść albo mogę pójść tutaj o alfa 2 w lewo, albo w prawo.
W któryś z tych dwóch. Powiedzmy, że poszedłem w lewo. Teraz jestem tutaj. Potem mam plus R3 alfa 3 i też mogę pójść albo tak albo tak. Jak alfy są równe 1 wszystkie to to jest taki po prostu najprostszy spacer losowy, że idę w prawo albo w lewo z prawdictwem 1/2 o 1. Jak są alfy, to po prostu na na jmie jest konkretna długość kroku, którą można zrobić w prawo albo w lewo. No i f to jest po prostu kwadrat odchylenia od od zera. Można było też, można było też za fa wziąć moduł, bo teraz ta nasza nierówność to jest po prostu powiedzenie, że tu jest wartość oczekiwana, tak? średnie arytmetycznym wyników zmiennej f b do potęgi n i to do potęgi 1 n mniejsze równe wartość oczekiwana f b do n + 1 do potęgi 1 n + p tak to jest to samo tylko napisane w innym języku mogłem za f b wziąć moduł wtedy miałbym ten moduł do 2nj tu miał moduł do 2 x n + pzej to jest ta sama nierówność po prostu ją trzeba spierwiastkować wtedy Tu będzie 2n w mianowniku i tu będzie 2 x n + 1 w mianowniku.
Częściej się myśli o modułach, ale to zależy kogo pytać. Także tak to zadanie to to była nierówność o o tym, że spacery losowe spełniają to, co spełnia każda zmienna losowa i zostało to przewymnażane i doprowadzone do takiej postaci, w której z której jak się chociaż raz w życiu widziało te napisy z multinomialami, tak to jest prosto znać. To jest kursowe, to się pojawia. Takie coś też się widzi przynajmniej raz w życiu. Moim nieskromnym zdaniem największa trudność poznawcza była w przekonaniu się, że tu, że to można powymnażać.
Tak. To znaczy, że zamiast mieć ten napis wersji wersji o takiej, w której mam y w której mam ten iloczyn indykatorów, to można je zmusić do tego, żeby ciągami geometrycznymi, bo ciągi geometryczne to ja umiem suować przeciwko multinomialom. Takich śmiesznych rzeczy, które są po prostu jeden albo zero, to dużo gorzej. A wystarczy je tylko przesunąć o o 1/, żeby były ciągiem geometrycznym. No tak naprawdę to ja gdybym był porządny to jako przygotowanie do tego rozumowania pokazał tak taki rachunkowy przez multinomiale dowód tego, binomiale dowód tego, że suma n po k dla k parzystych jest y jest jest równa sumie dla nieparzystych.
Tak, to jest takie archetypiczne rozumowanie. Od tego powinien był zacząć, że jak ja je odejmę, to dostaję właśnie sumę n po k - 1 do k, czyli 1- 1 do k. Tak, bo to jest razy 1 najstarsza sztuczka na świecie y do ntej, czyli zero. Tak, czyli zakładwałem ich różnicę przy pomocy ciągu geometrycznego, bo lubię sumować ciągi geometryczne przeciwko npokat. Tu jest to samo, tylko że tylko, że przecensorowany L razy tak naprawdę. Czy to jest moment, żeby nagrozić kota za to, że że nie rozdeptał klawiatury?
Nie powinienem go nagradzać, bo był strasznie wredny i robił wojnę domową, ale ale niech mu będzie. To to tyle. M.