Nech n>=2 je prirodzené číslo. Nájdite najväčšie číslo pn s nasledovnou vlastnosťou: Ak každá z udalostí A1,...,An má pravdepodobnosť 1/2, potom existujú rôzne indexy i,j také, že pravdepodobnosť súčasného nastatia udalostí Ai a Aj je aspoň pn. Formulujme túto úlohu aj bez použitia pravdepodobnosti (hoci máličko menej všeobecne): Pre n>=2 nájdite najväčšie také číslo pn, že ak zjednotenie n množín plochy 1/2 má plochu nanajvýš 1, tak plocha prieniku niektorej dvojice z týchto množín je aspoň pn.
Je zrejmé, že p2=0 a z ilustračného obrázku sa zdá, že p3=1/6. Viete to dokázať? Viete nájsť hodnotu pn pre niektoré (alebo aj všetky) čísla n>=4?
Poznámka 23.10.: Dnes ráno ma napadlo pomerne jednoduché trikové riešenie využívajúce niektoré základné poznatky z pravdepodobnosti. Hodnota p_n je prekvapivo jednoduchou funkciou počtu udalostí n, hoci výsledný vzorček je trochu odlišný pre párne a pre nepárne n.
Rozmýšlal som 2 minúty a môj typ je (2 - n)/(2-2n). Dokázať to zatiaľ neviem, je to len intuícia.
OdpovedaťOdstrániťNo, to asi nebude dobre, pretože pre n=3 dáva Tvoj vzorček 1/4 a na ilustračnom obrázku je znázornená situácia, kde je maximálna pravdepodobnosť prieniku akejkoľvek dvojice len 1/6. Vlastne z toho obrázka plynie, že p_3<=1/6.
OdpovedaťOdstrániťAle inak na Tvojej intuícii môže byť čosi správne. Moja momentálne najlepšia všeobecná dolná hranica na hodnoty p_n je totiž veľmi podobného tvaru.
Ako som teda prezradil, ani ja sám som si nie istý s odpoveďou pre všeobecné n (len pre n=2,3,4) a to som sa zamýšľal nad touto úlohou včera večer, keď ma napadla, možno aj hodinu).
q_i=p(A_i), q_ij=p(Ai \prienik A_j), atd
OdpovedaťOdstrániť1=q_1+...+q_n-q_12-...-q_(n-1,n)+ atd
pre n<=7 plati (n nad 3)>=(n nad 4), (n nad 5)>=(n nad 6) atd
teda (pre n<=7) 1>=q_1+...+q_n-q_12-...-q_(n-1,n)>=n/2-(n nad 2)p_n
teda p_n>=(n-2)/(n(n-1))
tak aspon nejaky odhad mam
pre n=3 je to prave 1/6 a z obrazka vyplyva rovnost p_3=1/6
takto pre n=4:
OdpovedaťOdstrániťzvolme q_ij=(n-2)/(n(n-1))(=p_n) q_ijk=0
nakreslime si taky obr ako pre tri
tie zvysky budu 1/2-(n-1)p_n=1/2-(n-2)/n=(4-n)/(2n)
co je pre n=4 este nezaporne pre vacsi to uz asi nepojde, dokonca si myslim, ze to p_n bude ine.
cize mame zatial, ze p_3=p_4=1/6
Braňo: Fajn. V Tvojom dôkaze by to však chcelo ešte trochu odôvodniť niektoré kroky (napríklad prečo stačí porovnávať veľkosti tých kombinačných čísiel, keďže tie kombinačné čísla určujú len počet sčítancov, alebo odčítancov). Naviac, dá sa ukázať, že podobná cesta je schodná pre akékoľvek n>=2, nielen pre n<=7.
OdpovedaťOdstrániťV zásade si použil tzv. Bonferroniho nerovnosť pre k=2, ktorá tvrdí, že pravdepodobnosť zjednotenia udalostí je väčšia rovná súčtu pravdepodobností jednotlivých udalostí mínus súčet pravdepodobností prienikov všetkých dvojíc. Na základe tejto nerovnosti je možné nájsť to Tvoje ohraničenie na p_n spôsobom, ktorý som stručne popísal v tomto súbore.
Pre n>=5 viem nájsť pokročilejšími trikmi ešte lepšie ohraničenie a taktiež viem nájsť jednoduché ohraničenie zhora pre každé n. Ale aká je presne hodnota p_n pre n>=5 zatiaľ neviem.
Každopádne je to celkom fajn problém; škoda, že v tomto období nemám viac času, aby som sa s ním pobavil. (Ale inak som si skoro istý, že už je dávno vyriešený. Takto jednoducho formulované úlohy sú už obvykle vyriešené nejakých 100 rokov a viac.)
Len malá poznámka: Už viem všeobecné riešenie. Pre človeka, ktorý ovláda základy vysokoškolskej pravdepodobnosti, nie je ťažké toto riešenie vysvetliť, hoci prísť na toto riešenie si vyžaduje trik. Tvar riešenia je veľmi jednoduchý.
OdpovedaťOdstrániťPekná úloha :-)
OdpovedaťOdstrániťJa som zatiaľ najlepšie dokázal vyrobiť (n-2)/(4(n-1)) pre párne n a
(n-1)/(4n) pre nepárne.
Pre párne to funguje tak, že posekáme plochu veľkosti 1 na {n nad (n/2)} rovnako veľkých častí a každú z nich označíme inou neusporiadanou (n/2)-prvkovou podmnožinou {1, 2, ..., n}. No a hľadané množiny A_1, ..., A_n budú potom tvorené zjednoteniami tých častí, ktorých označenie obsahuje ich index.
Napríklad tak pre n=6 máme 20 častí, s označeniami 123, 124, 125, 126, 134, 135, 136, 145, 146, 156, 234, 235, 236, 245, 246, 256, 345, 346, 356, 456. Prvých 10 z nich dohromady tvorí množinu A_1, časti 124, 134, 145, 146, 234, 245, 246, 345, 346, 456 dohromady tvoria množinu A_4, ...
Každá množina má celkovú plochu 1/2 a prienik hociktorej dvojice A_i, A_j (i rôzne od j) pozostáva z práve {(n-2) nad (n/2 - 2)} častí. Jeho plocha je potom taká, ako bolo napísané vo vzorčeku hore. No a pre nepárne n sa dá spraviť to, že sa vyrieši "párna" úloha pre (n+1) a jedna množina sa zahodí :-)
Z toho nám vychádza p_5, p_6 <= 1/5, p_7, p_8 <= 3/14.
Ale či to je optimálne, to som ešte nedoriešil :-)
Pekne goober. Musím si to spätne vyhľadať, ale mám silný dojem, že Tvoje riešenie je naozaj to optimálne. Dôkaz optimality som urobil špeciálnym trikom, ale určite sa dá urobiť veľa rôznymi spôsobmi...
OdpovedaťOdstrániťInak nezislo by sa povedat, ze tie mnoziny nesmu byt totozne? Pravdepodobnost pravdu povediac (s pravdepodobnostou p>.8 :) ) nebola moja krvna skupina tak mozna nieco prehliadam :) Ale ak tie mnoziny budu vzdy totozne tak riesenim je 0.5 :)
OdpovedaťOdstrániťRori: Nie, nie je to nutné napísať. V zadaní hľadáme maximálne číslo p(n), pre ktoré platí nasledovný výrok V(n): Ak máme n množín plochy 1/2, ktorých zjednotenie má plochu nanajvýš 1 (alebo udalostí pravdepodobnosti 1/2), tak prienik niektorých dvoch z týchto množín je aspoň p(n) (resp. pravdepodobnosť súčasného nastatia niektorých dvoch z týchto udalostí je aspoň p(n)).
OdpovedaťOdstrániťGoober našiel takú n-ticu množín plochy 1/2, že žiadny prienik po dvoch nemá plochu väčšiu ako (n-2)/(4n-4) pre párne n a (n-1)/4n pre nepárne n. Tým ukázal, že p(n) je nanajvýš toľkoto, lebo pre vyššiu hodnotu p(n) by už neplatil výrok V(n).
Ak by sme zobrali všetky množiny rovnaké, tak tým by sme ukázali, že p(n)<=1/2, ale to je (podstatne) slabšie tvrdenie o hodnote p(n) ako to gooberovo.
Keď som túto úlohu zadal, tak som našiel trikové riešenie, ktoré si musím spätne nájsť (momentálne som extremely busy), ale mám taký dojem, že tie gooberove hranice sú nielen horným ohraničením, ale priamo hodnoty p(n), čiže dá sa ukázať, že sa žiadne množiny plochy 1/2, ktorých zjednotenie má plochu nanajvýš 1, nedajú vymyslieť tak, aby aspoň jeden prienik nemal plochu minimálne toľko, koľko sú tie gooberove hranice.