Mat tretím ťahom: dva v jednom

Nasledovnú pozíciu som si poznačil asi pred desiatimi rokmi a nepamätám si presne ako som sa k nej dostal (buď sa mi objavila v hre, alebo som ju vyčítal z nejakej zbierky šachových úloh). Viem ale, že 2. verziu problému som vytvoril sám a to "omylom" tým, že som si naopak rozložil figúrky :-)

Biely je na ťahu a dá mat najneskôr svojim 3. ťahom

1. verzia: šachovnica je otočená z pohľadu bieleho;

2. verzia: šachovnica je otočená z pohľadu čierneho.

Táto moja "kompozícia" je len taký náhodný úkaz, ale inak na Slovensku máme veľmi silnú skupinu serióznych kompozičných šachistov. Jeden z nich je bývalý matfyzák a môj dlhoročný priateľ Juraj Lörinc.

Poznámka 30.11.: Ako zistil ruziklan vo svojej databáze šachových úloh (pozri komentáre), obidva tieto problémy boli publikované už v roku 1900 (Galickij). Takže žiadna originálna kompozícia to nie je :-)

Multivesmír, determinizmus a náhodnosť

Hneď na začiatku by som chcel upozorniť, že nie som fyzik, takže všetky moje nasledujúce špekulácie sú len čosi ako science fiction a treba ich brať s rezervou. S veľkou rezervou.

Predstavme si, že sme na superpočítači vytvorili svet obsahujúci mysliacu bytosť B. Keďže náš umelý svet je len kusom softwaru, nie je problém vytvoriť hocikoľko jeho identických kópií. Necháme teda skopírovať tento svet dvakrát, pričom do prvej z tejto dvojice kópií pridáme bit 1 a do druhej kópie pridáme bit 0, čím vzniknú svety B1 a B0. Následne vytvoríme dve kópie každého z týchto svetov a priradíme im bity tak, aby vznikli svety B11, B10, B01 a B00. Celý tento proces rozdvojenia mnohokrát zopakujeme, čím dostaneme svety B11...11, B11...10, ... , B00...00.

Ako budú naše bytosti vnímať svoje bity? Je zrejmé, že prevažná väčšina z nich ich bude vnímať ako dlhú náhodnú postupnosť výsledkov hodov mincou a to napriek tomu, že ich svet je z nášho pohľadu tvorený úplne deterministicky. Dokonca môžeme povedať, že pre väčšinu z týchto bytostí je náhodnosť najlepší možný model reality.

Podľa "mnohosvetovej" interpretácie kvantovej mechaniky sme my sami v podobnej situácii - v megavesmíre, ktorý sa v každom okamihu štiepi na nepredstaviteľné množstvo potomkov. Z pohľadu drvivej väčšiny týchto svetov - a asi aj toho nášho - je teda pravdepodobnosť integrálnou zložkou fyzikálneho popisu pozorovaní (zdanlivo spôsobujúcich kolaps vlnovej funkcie), hoci samotné pravdepodobnostné rozdelenie výsledkov týchto pozorovaní sa môže meniť deterministicky (pozri Schrödingerovu rovnicu).

Podľa mnohosvetovej interpretácie je nielen potenciálne možná akákoľvek budúcnosť (to je v zásade pravda aj pre klasickú kodaňskú interpretáciu), ale každá z týchto budúcností aj skutočne kdesi nastáva. To znamená, že existuje aj vesmír, v ktorom sa do detailov uskutočnil pre náš vesmír fiktívny príbeh Harryho Pottera. Nieže by som tomu veril, ale v princípe teda nemusí mať megavesmír vôbec žiadne pravidlá a my len zhodou okolností žijeme v takom, v ktorom sa nejaké tie pravidlá vyskytli, povedzme tak, aby umožňovali vznik vedomia (čosi ako antropický princíp). Skutočne; môže byť vôbec fyzika pri mnohosvetovej interpretácii logicky konzistentná? Ak by sme ju totiž akceptovali, tak automaticky pripúšťame, že akýkoľvek fyzikálny model vesmíru môže byť pomýlený.

Kvalitné odkazy na web: 1) Rozhovor na s Davidom Deutschom z Oxfordu (Spiegel); 2) Článok o mnohosvetovej interpretácii a o "teste" tejto interpretácie s Maxom Tegmarkom z Princetonu (NewScientist); Všeobecne o kvantovej fyzike v ľudskej reči (New York Times).

Odmocniny ortogonálnych matíc

Počas písania predchádzajúceho príspevku ma napadol nasledovný problém, tentokrát však z kategórie ťažkých (možno by bol jemne netriviálny aj pre mojich kolegov z algebry; teda aspoň ja ho neviem uspokojivo vyriešiť).

Nech k je prirodzené číslo a nech U je ortogonálna matica typu m krát m. Nájdite predpis pre počet a metódu konštrukcie všetkých ortogonálnych matíc V, pre ktoré platí U=V^k.

Keď som sa nad týmto problémom trochu zamyslel, dospel som k názoru, že práve takáto úloha môže byť vhodná na "kolektívne" riešenie. Urobme teda pedagogický experiment: Keď Vás napadne niečo nové a relevantné, napíšte to do komentáru a spoločne sa budeme snažiť prísť problému na kĺb. Ja sám sa nebudem snažiť tento problém intenzívne riešiť, iba možno občas napíšem nejaký motivačný postreh. Tiež sa nebudem pýtať na riešenie mojich kolegov, ktorí sa veľmi dobre v danej problematike orientujú, pretože vážne hrozí, že by nám úlohu hneď vyriešili a pokazili by nám radosť z objavovania :-) Možno sa nám podarí trochu poodhaliť kreatívny proces matematického uvažovania a pritom sa aj vzdeláme vo veľmi zaujímavej a dôležitej oblasti. Takže na úvod len niekoľko postrehov.

Postreh 1 (algebraický): Ak je k párne, tak je nutnou podmienkou existencie aspoň jednej k-tej odmocniny matice U rovnosť det(U)=1, t.j. U musí byť takzvanou špeciálnou ortogonálnou maticou, resp. maticou rotácie. Dôkaz: Všimnime si, že determinant akejkoľvek ortogonálnej matice V môže byť iba +1 alebo -1: Z definície ortogonality V máme VV^T=I, kde I je jednotková matica a zo základných vlastností determinantu máme

1=det(I)=det(VV^T)=det(V)det(V^T)=det(V)².

Teda det(U)=det(V^k)=det(V)^k=1. QED.

Postreh 2 (geometrický): Ak by sme hľadali riešenia V s determinantom 1, tak vlastne hľadáme takú "rotáciu" V, ktorej k-násobným opakovaným použitím dostaneme zadanú "rotáciu" U. Dá sa ale tušiť, že každá rotácia U sa dá poskladať z k-opakovaných rotácií V, t.j. naša domnienka je, že det(U)=1 je postačujúcou podmienkou na existenciu aspoň jednej k-tej odmocniny matice U.

Postreh 3 (algebraický): Pre niektoré ortogonálne matice U existuje viac ako jedna k-ta odmocnina: Napríklad, ako jednotková matica I, tak aj matica -I je ortogonálna a platí I=I.I, ale aj I=(-I)(-I).

Postreh 4 (4.12.07): Už pre jednotkovú maticu I typu 2x2 existuje nespočítateľne veľa druhých odmocnín! Ako sa dá ľahko skontrolovať, pre každé reálne θ je nasledovná matica ortogonálna druhá odmocnina matice I.



Postreh 5 (5.12.07). Predchádzajúca matica je len špeciálny prípad širokej triedy ortogonálnych druhých odmocnín jednotkovej matice I typu mxm. Môžete si skontrolovať, že ortogonálnou druhou odmocninou matice I je každá matica V tvaru

kde u₁,...,u_m je systém navzájom kolmých vektorov dĺžky 1 a i₁,...,i_m sú 0 alebo 1. To teda znamená, že jednotková matica mxm pre akékoľvek m>=2 má nekonečne veľa ortogonálnych druhých odmocnín.

A ako som na tento predpis pre V prišiel? Ako je to so zdanlivo komplikovanými matematickými vzorcami časté, myšlienky, ktoré k nim vedú, sú založené na veľmi jednoduchých geometrických predstavách, analógiách a mechanických formálnych postupoch. (Niekedy je však ťažké tieto postupy zrozumiteľne popísať. Na druhej strane občas akoby niektorí prehnane ctižiadostiví matematici svoje postupy zámerne tajili aby sa mohli vyťahovať svojimi úžasnými formulkami. Podobne ako David Copperfield neprezradí sériu triviálnych fínt, na ktorých sa zakladá na prvé videnie prekvapivý výsledný efekt :-)

Takže najprv som si uvedomil, že matica z Postrehu 4 zodpovedá preklopeniu roviny okolo nejakej priamky prechádzajúcej počiatkom súradnicovej sústavy. To je ale taká transformácia roviny, ktorá nechá jednotkový smerový vektor u danej priamky nezmenený a druhý jednotkový vektor, kolmý na u, preklopí na opačný. Analogické transformácie sa predsa dajú skonštruovať v ľubovoľnom priestore! Ak by sme mali akýkoľvek systém navzájom kolmých jednotkových vektorov, tak môžeme vytvoriť transformáciu, ktorá niektoré z týchto vektorov preklopí a iné nechá nezmenené. Je úplne zrejmé, že dvojnásobné použitie tejto transformácie opäť vráti všetky vektory do pôvodnej polohy! Je už len záležitosťou základnej techniky lineárnej algebry z prvého ročníka formálne zapísať maticu V, ktorá tomuto preklápaniu zodpovedá.

Čo sa teda týka ortogonálnych druhých odmocnín jednotkových matíc, tento špeciálny prípad pôvodného problému už máme skoro vyriešený, hoci ešte by sme sa mohli spýtať, či existujú aj ortogonálne druhé odmocniny jednotkovej matice, ktoré nie sú typu matice V popísanej vyššie. (Tipol by som si, že nie.) Trochu ťažšie, ale stále nie úplne všeobecné otázky sú nasledovné: Ako skonštruovať triedu všetkých k-tych odmocnín jednotkovej matice pre k>2? Je množina všetkých tretích ortogonálnych odmocnín jednotkovej matice typu 2x2 konečná, alebo je nekonečná? Ako skonštruovať druhú odmocninu z akejkoľvek zadanej ortogonálnej matice (s determinantom 1)?

...

Máte nejaké nápady?

Rotácia telies

Na prednáške sme sa dnes rozprávali o rotáciách telies, čo ma inšpirovalo k napísaniu programíku, ktorý rotuje množinu trojrozmerných bodov. Použil som nasledovnú primitívnu metódu.

Zostrojíme matice R_x(α) , R_y(β), R_z(γ), zodpovedajúce rotáciám "okolo" jednotlivých osí o uhly α, β, γ - pozri vzorce (4), (5), (6) na tejto stránke mathworldu.

Trojrozmerná rotácia zobrazená na i-tom frame animácie zodpovedá ortogonálnej matici

V_i= R_x(α)ⁱ R_y(β)ⁱ R_z(γ)ⁱ.

Ak vhodne volíme počet framov a uhly α, β, γ, tak sa nám teleso "otočí zo všetkých strán" a rotácia telesa sa naviac pekne uzavrie, takže animáciu môžeme pustiť v slučke. Ja som na vygenerovanie nasledovného obrázku volil 48 framov a

α=π/8, β=π/12, γ=π/24.

Ako množinu zrotovaných bodov som zobral body na povrchu dvoch zakliesnených tórusov (Pozri predchádzajúci post). Upozorňujem, že výsledný animovaný gif má 2MB (mal by sa spustiť kliknutím na obrázok).

Samozrejme, oveľa efektnejšie by bolo použiť väčší počet framov (súčasne menšie uhly α, β, γ), "plné" telesá a prepočítavať viditeľnosť atď, ale princíp uzatvorenej slučky rotácií je jasný aj na takomto jednoduchom obrázku.

Poznámka: Ak sa niekomu chce, mohol by skúsiť naprogramovať týmto spôsobom rotáciu tanečnice (alebo podobne zaujímavého objektu :). Očakávam, že ortogonálny (t.j. bez perspektívy) priemet akokoľvek komplikovanej rotácie by sa dal mentálne interpretovať dvomi spôsobmi, podobne ako v prípade slávnej tanečnice.

Náhodné body na tóruse

Štyri pohľady na 10000 vygenerovaných náhodných bodov s rovnomerným rozdelením na povrchu tórusu.


Ak chcete vedieť detaily, pozrite si môj program v jazyku R.

Zacyklený milionár

V dvoch tučných nepriehľadných obálkach sú peniaze, pričom viem, že v jednej z týchto obálok je dvojnásobok sumy v druhej obálke. Dostal som možnosť vybrať si ľubovoľnú z týchto dvoch obálok a peniaze z nej si ponechať. Avšak akonáhle jednu obálku otvorím, už sa nemôžem rozhodnúť pre tú druhú.

Náhodne som si zvolil jednu obálku, no tesne pred otvorením ma napadla výborná myšlienka. Moja obálka obsahuje sumu X a ja s istotou viem, že tá druhá obálka obsahuje sumu X/2, alebo sumu 2X. To znamená, že ak si vyberiem tú druhú obálku, môžem v porovnaní s momentálnym stavom stratiť X/2, ale získať môžem až X. Zjavne je výhodné zobrať si tú druhú obálku! Potešil som sa svojej bystrej úvahe a obálky som si vymenil. Už som sa chystal preveriť si svoj zisk, no v tom ma napadla ďalšia výborná myšlienka. Moja obálka obsahuje sumu X ...

Obálky si vymieňam dodnes. Občas mi síce v hlave vŕta iracionálny červík pochybnosti, ale moje logické úvahy sú predsa nepriestrelné. Alebo nie?

Poznámka: Tento problém patrí k matematickému folklóru (pozri link v komentároch); moja vlastná je len jeho formulácia :-)

Delenie zlatého prútu II

Predpokladajme rovnakú situáciu ako v predošlom príspevku, avšak s nasledovnými možnosťami výberu Vášho úlomku: a) Dostanete najmenší z úlomkov; b) Dostanete polovicu z druhého najväčšieho úlomku. Ktoré pravidlo by ste si vybrali?

Poznámka: Predpokladáme, že deliace body vyberáme nezávisle a rovnomerne náhodne na celom prúte. Inak tento príklad je ťažší (a odpoveď je menej jednoznačná) ako v predchádzajúcom príspevku; dôvody však nebudem zatiaľ rozoberať.

Poznámka 13.11.: V komentároch už máme správne riešenie založené na simuláciách; zaujímavé by však bolo aj presné (analytické) riešenie. Podujme sa na to niekto?

Delenie zlatého prútu I

Zlatý prút bude rozdelený na tri úlomky dvomi náhodnými rezmi, pričom jeden z týchto úlomkov máte dostať Vy. Môžete si vopred zvoliť jedno z nasledovných pravidiel výberu Vášho úlomku: a) Dostanete "prostredný" úlomok, t.j. ten, ktorý neobsahuje ani jeden z okrajov pôvodného prútu; b) Dostanete ten úlomok, na ktorom leží stred pôvodného prútu. Ktoré z týchto dvoch pravidiel je pre Vás výhodnejšie? Alebo sú obe pravidlá "ekvivalentné"?

Poznámka: Úlohu už máme vyriešenú - pozri komentáre.

Netranzitívne kocky

Pre dve kocky K a L s očíslovanými stenami označme symbolom P[K>L] pravdepodobnosť, že pri súčasnom hode týmito kockami padne na kocke K väčšie číslo ako na kocke L. Nájdite očíslovanie strán troch kociek A,B,C tak, aby súčasne platilo:

P[A>B]>1/2, P[B>C]>1/2, P[C>A]>1/2.

Poznámka: Tento príklad partí k pravdepodobnostnému "folklóru". Zaujímavejšou a ťažšou úlohou je nájsť očíslovania štyroch kociek A,B,C,D, pre ktoré platí P[A>B]>1/2, P[B>C]>1/2, P[C>D]>1/2 a P[D>A]>1/2.

Pravdepodobnosť a demokracia

Prvý príklad z klasickej zbierky pravdepodobnostných príkladov od Fredericka Mostellera znie nasledovne: Traja sudcovia A,B a C nezávisle rozhodujú medzi dvomi alternatívami. Vieme, že pravdepodobnosť pA správneho rozhodnutia sudcu A je rovnaká ako pravdepodobnosť pB správneho rozhodnutia sudcu B, t.j. pA=pB=p. Sudca C však založí svoje rozhodnutie na hode mincou, čiže jeho pravdepodobnosť správneho rozhodnutia je pC=1/2. Výsledné rozhodnutie poroty bude také, za ktoré bude hlasovať väčšina sudcov. S akou pravdepodobnosťou dospeje porota k správnemu rozhodnutiu? Odpoveď je presne p, čiže náš „flippant juror“ C úplne eliminuje vplyv jedného zo sudcov A a B. Tým Mostellerov príklad končí.

My však poďme trochu ďalej a položme si otázku: "Aká by bola situácia, ak by bol sudca A lepší než sudca B, napríklad ak by sme mali pA=90%, pB=89,9% a pC=50%"? Dá sa ľahko ukázať, že potom by optimálnou rozhodovacou stratégiou poroty ako celku bolo rozhodovať len na základe sudcu A, t.j. úplne ignorovať hlas nielen mincového sudcu C, ale aj relatívne veľmi dobrého sudcu B. Ako je to teda vo všeobecnosti s výberom optimálnej skupinovej stratégie rozhodovania troch sudcov v závislosti od ich pravdepodobností správneho rozhodnutia pA, pB a pC?

Všetkých stratégií skupinového rozhodovania trojčlennej poroty je, v istom dobre definovanom zmysle, 256 a pre každú kombináciu pravdepodobností pA, pB, pC je možné nájsť tú najlepšiu stratégiu metódou "hrubej sily" na počítači. Keď položíme pevne pA=0,75 a pre rôzne kombinácie hodnôt pB a pC v rozmedzí 0,5 až 1 farebne zaznačíme optimálnu stratégiu, dostaneme nasledovný obrázok.


Farby oranžová, červená a žltá zodpovedajú situáciám, kedy je optimálne ignorovať všetkých okrem toho, kto správne rozhoduje s najväčšou pravdepodobnosťou. (Predstavte si napríklad rodiča s dvomi malými deťmi :-) Modrou farbou je zobrazená oblasť tých dvojíc (pB,pC), pri ktorých je optimálnym „demokratický“, t.j. väčšinový rozhodovací systém. Vidíme, že tento systém je optimálny, voľne povedané, v prípade, že sú všetci traja podobne, ale zďaleka nie nutne rovnako dobrí. Všimnite si napríklad, že bod so súradnicami (0,72; 0,69) leží v modrej oblasti, takže pre pA=0,75, pB=0,72 a pC=0,69 je optimálnym väčšinový rozhodovací systém.

Na nasledovnom obrázku sú znázornené pravdepodobnosti správnych rozhodnutí poroty pri optimálnej stratégii skupinového rozhodovania (opäť v závislosti od pB a pC pri pevnom pA=0,75).
Z obrázku a aj bez neho je zrejmé, že žiadna stratégia plne založená na rozhodovaní len jediného človeka nemôže priniesť kvalitu rozhodovania lepšiu ako je kvalita samotného "diktátora". To sa ale nedá povedať o demokratickej rozhodovacej stratégii. V súlade s intuíciou aj našim modelom, demokratická stratégia vedie k takému rozhodovaniu celej skupiny, ktoré môže byť podstatne kvalitnejšie, než umožňujú schopnosti ktoréhokoľvek zúčastneného jednotlivca.

Poznámky: Pochopiteľne na hraniciach medzi oblasťami prislúchajúcimi rôznym optimálnym stratégiám je súčasne optimálnych viacero stratégií. Najzaujímavejší je tento fenomén asi v bodoch, kde sa stretávajú dve "diktátorské" optimálne stratégie s demokratickou optimálnou stratégiou (zelené bodíky). Inak teoreticky zaujímavé, ale asi pomerne ťažké, by bolo študovať optimálne stratégie pre počet sudcov väčší ako 3. Počet všetkých stratégií pre n sudcov je 2 na (2 na n), čiže už pre povedzme n=7 neprichádza výpočet hrubou silou do úvahy.
Poznámka 8.11.: Kuriózne optimálne stratégie skupinového rozhodovania vznikajú vtedy, keď niektorí zo sudcov majú pravdepodobnosť správneho rozhodnutia menšiu ako 50%. Napríklad ak pA=80%, pB=15% a pC=50%, potom je najlepšou stratégiou rozhodovania ignorovať sudcov A, C a ako výsledok zobrať opačné rozhodnutie ako je rozhodnutie sudcu B :-)