Chlapec, dievča a pes

Nasledovná úloha pripomína príklady pre stredné školy. Nebude problém vyriešiť ju úplne mechanicky. Alebo áno?

Chlapec, dievča a pes vychádzajú zo spoločného bodu na rovnej ceste, pričom chlapec pôjde celý čas rýchlosťou 6 kilometrov za hodinu, dievča 4 kilometre za hodinu a pes bude kmitať medzi chlapcom a dievčaťom rýchlosťou 10 kilometrov za hodinu. (T.j. keď pes dobehne chlapca, tak sa okamžite otočí a bude bežať konštantnou rýchlosťou 10 km/hod k dievčaťu, keď dobehne k dievčaťu tak sa okamžite otočí a bude bežať konštantnou rýchlosťou 10 km/hod ku chlapcovi a tak ďalej.) Ako ďaleko od štartu sa bude nachádzať pes po jednej hodine?

Táto úloha je z už viackrát spomínanej knihy Martina Gardnera. Teším sa na Vaše riešenia.

Presviedčacia sila faktu

Matematický aparát teórie pravdepodobnosti obvykle používame na kvantifikáciu "objektívnej neurčitosti" týkajúcej sa výsledkov experimentu. V tomto príspevku však budeme interpretovať pravdepodobnosť tak, ako ju vidia Bayesisti, t.j. ako mieru "subjektívnej dôvery" v pravdivosť hypotéz.

Predstavme si napríklad, že rozhodca hodil mincou. Napriek tomu, že o výsledku tohto hodu je už rozhodnuté, z môjho subjektívneho hľadiska je miera dôvery, že padol znak, rovná 1/2. To platí až do okamihu, keď o výsledku získam nejakú informáciu. Až vtedy sa moja subjektívna miera dôvery zmení a to v závislosti od toho, akú informáciu som získal. Napríklad ak by som sa na vlastné oči presvedčil, že padol znak, tak sa moja miera dôvery zmení na jednotku a ak by mi tento výsledok len niekto oznámil, tak by sa moja subjektívna miera dôvery v to, že padol znak, mohla zmeniť na hodnotu nižšiu ako jedna. V tomto druhom prípade by totiž jediným úplne istým faktom bolo pre mňa to, že mi nejaký človek oznámil, že padol znak, čo je, ako uznáte, nie vždy to isté, ako že znak naozaj padol.

Vo všeobecnosti môžeme teda povedať, že akonáhle sa človek dozvie novú informáciu, nastane zmena jeho osobného pravdepodobnostného modelu sveta.

Pre človeka c označme symbolom Pc jeho pravdepodobnostný model sveta a nech H je nejaká hypotéza. Ako Pc(H) označíme mieru dôvery človeka c v platnosť hypotézy H, čo je číslo medzi 0 a 1. Pochopiteľne, Pc(H)=1 znamená, že c si je istý, že H platí a Pc(H)=0 znamená, že c si je istý, že H neplatí. Slovným spojením "preferencia hypotézy H človekom c pred negáciou hypotézy H", alebo stručnejšie "preferencia hypotézy H" nazveme hodnotu


kde !H je označenie logickej negácie hypotézy H. (Kladieme log(0/1)=-∞ a log(1/0)=+∞.) Všimnite si, že čím je väčšia miera dôvery Pc(H), tým je väčšia aj preferencia (H:!H)c a naopak, avšak preferencia môže na rozdiel od dôvery nadobúdať všetky možné číselné hodnoty, ako kladné, tak aj záporné. Naviac, preferencia hypotézy s pravdepodobnosťou 1/2 (pred jej negáciou) je nulová, čo je plne v súlade s intuitívnou predstavou o tomto pojme.

Dá sa ukázať, že ak človek dodržuje všetky pravidlá racionálneho uvažovania, tak sa jeho preferencia hypotézy H musí po zistení faktu F zmeniť nasledovne:


kde Pc(F|H) (a Pc(F|!H)) je miera očakávania platnosti faktu F za predpokladu, že by hypotéza H bola pravdivá (resp. bola nepravdivá). Pravý člen vo vzťahu vyššie teda určuje o koľko fakt F zmení človeku c preferenciu hypotézy H. Túto hodnotu môžeme teda nazvať "presviedčacia sila" faktu F v prospech hypotézy H.

Všimnime si, že fakt F zvyšuje presvedčenie človeka c o platnosti hypotézy H vtedy, keď je pre neho fakt F očakávateľnejší za predpokladu platnosti hypotézy H, než za predpokladu neplatnosti hypotézy H.

Pozrime sa na niekoľko príkladov:

Človek: Ja. Fakt: Moja manželka mi oznámila, že vonku prší. Hypotéza: Vonku naozaj prší. Presviedčacia sila faktu o danej hypotéze: Hodnota Pc(F|H), t.j. moje očakávanie, že mi manželka oznámi, že prší, ak naozaj prší, nie je nijako vysoká. Ale hodnota Pc(F|!H), t.j. pravdepodobnosť, že mi manželka oznámi, že prší, ak by v skutočnosti nepršalo, je extrémne nízka (zrak má dobrý a zmysel pre humor má normálny). Pomer týchto hodnôt je teda veľké číslo a preto aj presviedčacia sila daného faktu o tom, že prší, je veľmi vysoká.

Človek: Ja. Fakt: Vidím nejaký lietajúci tanier. Hypotéza: Vidím lietajúci tanier, v ktorom sú skutoční mimozemšťania. Presviedčacia sila faktu o danej hypotéze: Ak by som videl lietajúci tanier, v ktorom sú skutoční ufóni, tak je logicky jasné, že by som videl nejaký lietajúci tanier, t.j. Pc(F|H)=1. Avšak ak by aj nebola pravda, že vidím lietajúci tanier, v ktorom sú skutoční mimozemšťania, tak pravdepodobnosť, že vidím nejaký lietajúci tanier, nie je zďaleka 0, t.j. Pc(F|!H)>>0. (Môj pravdepodobnostný model totiž zahŕňa ten fakt, že sa nachádzam v zábavnom parku Gardaland.) Presviedčacia sila daného faktu o hypotéze skutočných mimozemšťanov je teda nenulová, ale pomerne malá a vzhľadom na moju mizivú apriórnu dôveru v UFO ma žiadna hystéria nechytá. (Iná situácia by však bola, ak by som sa práve nachádzal na Chopku).

Človek: Ja. Fakt: Nemenovaný politik odpovedal na otázku, či mu záleží na blahobyte občanov, odpoveďou "áno". Hypotéza: Tomuto politikovi naozaj záleží na blahobyte občanov. Presviedčacia sila faktu o danej hypotéze: Pravdepodobnosť Pc(F|H), že politik povie, že mu záleží na blahobyte občanov, ak mu na ňom naozaj záleží, je 1. Avšak pravdepodobnosť Pc(F|!H), že to povie, ak mu na blahobyte občanov nezáleží, je tiež 1. Keďže log(1/1)=0, presviedčacia sila daného faktu o nesebeckých pohnútkach politika je nulová.

Disjunktné párovanie

S knihou sa nenudím ani počas niekoľkohodinového čakania a ak aj nemám knihu, nie je problém sa príjemne zabaviť - len tak v mysli. Minule ma počas dlhej cesty autom (samozrejme keď som nešoféroval!) napadla takáto úloha:

Predpokladajme, že v rovine máme párny počet bodov. Zdá sa intuitívne zrejmé, že tieto body môžeme pospájať úsečkami do dvojíc tak, aby sa žiadne dve z týchto úsečiek nepretínali. Vedeli by ste vymyslieť úplne jasný dôkaz, že to je naozaj tak? A vedeli by ste popísať nejaký efektívny algoritmus, ktorý také párovanie bodov nájde?

Najmenšia vzdialenosť dvoch bodov

V práci môjho bakalára sa vyskytol nasledovný okrajový, ale celkom zaujímavý algoritmický problém:

Vstupom je n vektorov x₁,...,x_n v m-rozmernom Euklidovskom priestore. Cieľom je zistiť Euklidovskú vzdialenosť dvoch najbližších bodov, t.j. vypočítať hodnotu

Otázkou je, či je možné skonštruovať asymptoticky rýchlejší algoritmus, než výpočet vzdialeností medzi všetkými n(n-1)/2 dvojicami rôznych bodov.

Poznámka: Sám neviem na tento problém odpovedať v plnej všeobecnosti (vlastne len pre m=1), takže neviem ani odhadnúť, aký je vo všeobecnosti náročný. Naviac, som si takmer istý, že tomuto jednoducho formulovanému problému sa už ľudia venovali, takže vyriešený už asi je. To nám však nebráni, aby sme sa nad ním zamysleli.

Vymyslené hádzanie II

Základný kurz z počítačovej štatistiky som tento semester učil iba druhýkrát a preto si ho stále ešte len vylaďujem. Napadlo ma, že by som ako súčasť hodnotenia predmetu mohol experimentálne zaviesť novinku: domácu úlohu, v ktorej si študenti vyskúšajú nielen to, ako dáta štatisticky spracovávať, ale aj čo obnáša ich získavanie. Vymyslel som teda niekoľko zadaní, v ktorých si študenti musia vytvoriť vlastné dátové súbory z veľmi jednoduchých, no úplne reálnych experimentov, alebo prieskumov. Naviac, experimenty sú navrhnuté tak, aby ich moji štatistici-začiatočníci vedeli spracovať pomocou obmedzeného repertoáru techník, ku ktorým sa počas semestra dostaneme. V tomto príspevku okomentujem výsledky jedného z týchto experimentov.

Mince. V tejto úlohe bolo potrebné najprv "mentálne" simulovať náhodnosť; presnejšie, vysloviť postupnosť symbolov H (hlava) a Z (znak) s cieľom čo najvernejšie napodobňovať výsledky nezávislých hodov mincou a potom rôznymi štatistickými testami otestovať hypotézu, že daná postupnosť zodpovedá reálnemu hádzaniu. Inými slovami, kladieme si otázku, či vie človek mentálne napodobniť náhodnosť, alebo sa nutne prejavia psychologické faktory, ktoré umožnia odhaliť, že sa nejedná o skutočný generátor náhodnosti.

Mentálne simulovanie hádzania mincou robili dve študentky; každá z nich nadiktovala sériu 240 výsledkov. Prekvapivo, jedna zo študentiek vygenerovala tak dokonalú náhodnú postupnosť, že použité testy na nej neodhalili absolútne žiadne anomálie. (A aj pre druhú študentku len jeden test "potvrdil", že sa nejedná o pravú náhodnosť. Slovo potvrdil som dal do úvodzoviek, pretože štatistická analýza nám nikdy neumožňuje robiť uzávery s absolútnou istotou.)

Dievčatá si (aj) za túto úlohu odo mňa odniesli A-čko a ja som si z tejto úlohy odniesol niekoľko poznatkov. Predovšetkým, pod ťarchou experimentálnych dôkazov musím zmierniť moju istotu, s ktorou som kedysi napísal príspevok "Vymyslené hádzanie".

Poznámky: Obrázok vľavo hore je z môjho predmetu "simulačné metódy", ale na "počítačovej štatistike" to vyzerá veľmi podobne. Inak ak budete mať záujem, môžem okomentovať aj výsledky ďalších úloh.

π

Ako ste možno zaregistrovali, včera prebehla médiami informácia o tom, že sa istému 13 ročnému žiakovi z Banskej Bystrice podarilo zapamätať si číslo π na 300 desatinných miest, čím vytvoril nový slovenský rekord. Gratulujeme.

Každopádne, najlepšie svetové výkony v tejto "disciplíne" sa pohybujú v úplne iných rádoch. V súvislosti s fenomenálnou pamäťou Vám odporúčam pozrieť si veľmi zaujímavé videá o Danielovi Tammetovi a o Kimovi Peekovi; je ohromujúce, čoho je ich mozog, a možno principiálne aj mozog každého z nás, schopný.

Tento príspevok som však začal písať s cieľom formulovať pre Vás nasledovnú úlohu: Predstavme si, že si budeme musieť zapamätať postupnosť povedzme 15 cifier. Nebudeme si môcť pritom vôbec nič poznačiť, avšak môžeme použiť akúkoľvek mnemotechnickú pomôcku, ktorú si vopred pripravíme (a budeme ju môcť používať ako pri zapamätávaní si, tak aj pri rekonštruovaní danej postupnosti čísiel). Máte nejaké nápady, akú pomôcku by ste si pripravili Vy?

Banachov-Tarskeho paradox: časť 2: úloha

Nech A je kružnica s polomerom 1 a nech B je tiež kružnica s polomerom 1, ktorej však chýba jeden bod (pozri obrázok). Sú množiny A a B zhodne rozložiteľné? T.j., trochu nepresne formulované: Je možné rozbiť A na konečný počet podmnožín, z ktorých len posunutím a rotáciou môžeme poskladať B?

Poznámka: Pojem "zhodne rozložiteľné množiny" sme presne definovali v predchádzajúcom príspevku. Teším sa na Vaše riešenia.

Banachov-Tarskeho paradox: časť 1: formulácia

Toto je prvý v sérii príspevkov, ktorými sa pokúsim ozrejmiť Banachov-Tarskeho paradox, ako som kedysi sľúbil. Čiastočne sa pritom budem držať knihy Leonarda Wapnera "The Pea and the Sun". Na začiatok úplne postačí, keď sa nám podarí pochopiť presné znenie tohoto paradoxu. Potrebujeme k tomu niekoľko matematických definícií na úrovni obtiažnosti nepresahujúcej prvý ročník na matfyze.

Nech Eⁿ je Euklidovský priestor, napríklad priamka (pre n=1), rovina (pre n=2), alebo klasický trojrozmerný priestor (pre n=3). Nech v je vektor v Eⁿ a nech U je matica rotácie typu nxn. Zobrazenie f, ktoré priradí každému bodu x v Eⁿ bod x+v, nazveme translácia (posun) a zobrazenie g, ktoré priradí každému bodu x v Eⁿ bod Ux nazveme rotácia (pootočenie). Ľahko si uvedomíme, že rotáciou v E¹ je len jediné zobrazenie a to identické. Každú rotáciu v E² si môžeme predstaviť ako pootočenie okolo bodu (0,0) a každú rotáciu v E³ si môžeme predstaviť ako pootočenie okolo nejakej priamky prechádzajúcej bodom (0,0,0).

Nech f je posun o vektor v, nech g je rotácia definovaná maticou rotácie U a nech M je nejaká množina v Eⁿ. Transláciou f množiny M nazveme množinu všetkých bodov tvaru x+v, kde x je bod z M a rotáciou množiny M nazveme množinu všetkých bodov tvaru Ux, kde x je bod z M. Ako príklad som na nasledovnom obrázku načrtol modrým transláciu f(M) zelenej množiny M o vektor (2,1) a ružovým rotáciu g(M) množiny M o uhol α=π/4 (t.j. o 45 stupňov).


Rozkladom množiny M nazývame každý systém M₁,...,M_k navzájom disjunktných podmnožín množiny M, ktorých zjednotenie je M. Dve množiny A a B v priestore Eⁿ nazveme zhodne rozložiteľné, ak existuje rozklad A₁,...,A_k množiny A a rozklad B₁,...,B_k množiny B tak, že pre každé i=1,...,k je množina B_i zrotovaná a posunutá množina A_i, t.j. existujú translácie f₁,...,f_k priestoru Eⁿ a rotácie g1,...,gn priestoru Eⁿ, že pre všetky i=1,...,n platí B_i=f(g(A_i)). To, že sú množiny A a B zhodne rozložiteľné, označíme A~B.

Čiže, veľmi voľne povedané, A~B znamená, že A je možné rozbiť na kúsky, z ktorých len posunutím a zrotovaním môžeme poskladať B. Ako príklad som načrtol obrázok dokazujúci A~B pre pravouhlý rovnoramenný trojuholník A (bez jednej odvesny) a štvorec B (bez jednej strany) s rovnakým obsahom ako má A.

Pripomeňme ešte, že pod pojmom guľa v E³ s polomerom r a stredom v bode P rozumieme množinu tých bodov E³, ktorých vzdialenosť od P je menšia, alebo rovná r.

Znenie Banachovho-Tarskeho paradoxu (vo formulácii nazývanej ''pea and the Sun''): Akékoľvek dve gule v E³, nie nutne s rovnakým polomerom, sú zhodne rozložiteľné.


Banachov-Tarskeho paradox je teda (dokázateľne platné) matematické tvrdenie že, voľne povedané, akúkoľvek malú trojrozmernú guľu vieme rozbiť na konečný počet podmnožín, z ktorých len pootočením a posunutím vieme poskladať (plnú) guľu s akokoľvek veľkým polomerom. Vaše prípadné nejasnosti a námietky napíšte do komentárov a ja sa Vám ich pokúsim vysvetliť resp. odmietnuť :)