Paradoks Montyja Halla

JavaScript simulacija problema. (Ispisuje se samo prvih 600 ponavljanja.)

Paradoks Montyja Halla

Problem Montyja Halla je vjerojatnosna zagonetka koja se temelji na igri u okviru američkog show programa „Let's Make a Deal“. Paradoks Montyja Halla dobio je ime po domaćinu showa, Montyju Hallu.

Zamislimo da u TV igri na sreću biramo jedna od triju zatvorenih vrata. Iza samo jednih nalazi se nagrada. Nakon što izaberemo vrata, voditelj otvori jedna od ostalih vrata, pokaže da iza njih nema nagrade, te nas pita želimo li promijeniti izbor. Imamo li veće šanse za pobjedu ako promijenimo izbor?

Budući da igrač ne zna koja od preostalih vrata kriju nagradu, većina će pretpostaviti da je svejedno koja od zatvorenih vrata izaberemo, te da nema razloga mijenjati izbor. U biti, u uobičajenoj interpretaciji problema (voditelj zna iza kojih vrata je nagrada i neće je pokazati), igrač bi trebao promijeniti izbor jer time šansu za pobjedu povećava s \frac{1}{3} na \frac{2}{3}.

Problem je u biti zabuna pri računanju vjerojatnosti otvaranja vrata s nagradom u danim uvjetima. Ovdje smo ga uvrstili zbog njegove popularnosti i činjenice da je čak i neke poznate matematičare bilo teško uvjeriti u točnost rješenja.

Kad je 1990. godine rješenje objavljeno u časopisu Parade, tisuće čitatelja poslale su žalbe tvrdeći da je objavljeni rezultat netočan. U odgovoru, autorica članka pozvala je sve nastavnike matematike u školama da s učenicima naprave sličan pokus sa šalicama i novčićem. Trebali su 200 puta odigrati situaciju pogađanja bez promjene nakon otkrivene prazne šalice, a zatim 200 puta s promjenom izbora.

Jedan način kako točno rješenje može postati više intuitivno je zamisliti isti slučaj sa 100 vrata, gdje nakon što izaberemo jedna, voditelj otvori još 98 i pokaže da iza njih nije nagrada. Sad se nekako čini da su ipak šanse da smo prvi put izabrali jedna od krivih vrata (vjerojatnost za to je 99%) i da je dobra ideja promijeniti odluku.

Pogledajmo jedno matematičko rješenje tog problema.

Rješenje s pomoću Bayesove formule

Zadatak: Zadana su vrata označena brojevima 1, 2 i 3. Iza jednih je nagrada. Pretpostavimo da smo izabrali vrata broj 1. Voditelj, koji zna gdje je nagrada i neće otvoriti ta vrata, otvori druga vrata. Tada nam ponudi da promijenimo prvi izbor. Hoće li u ovom trenutku promjena izbora povećati vjerojatnost pobjede?

Rješenje. Označimo događaje da je nagrada iza danih vrata s A_1, A_2 i A_3. Tada je P(A_1) = P(A_2) = P(A_3) = \frac{1}{3}. Radi jednostavnosti, pretpostavimo da smo već izabrali prva vrata. Označimo događaje da je voditelj otvorio jedna od zatvorenih vrata sa B_1, B_2 i B_3. Voditelj neće otvoriti vrata koja smo već izabrali, pa je P(B_1) = 0. Bez prethodnog znanja o mjestu nagrade, svakom od događaja B_2 i B_3 pridružit ćemo vjerojatnost 50%: P(B_2) = \frac{1}{2} i P(B_3) = \frac{1}{2}.

• Ako je nagrada iza vrata broj 1, voditelj slučajno bira između vrata 2 i 3: P(B_2|A_1) = \frac{1}{2} i P(B_3|A_1) = \frac{1}{2}.
• Ako je nagrada iza vrata broj 2, voditelj mora otvoriti vrata broj 3: P(B_2|A_2) = 0 i P(B_3|A_2) = 1.
• Ako je nagrada iza vrata broj 3, voditelj mora otvoriti vrata broj 2: P(B_2|A_3) = 1 i P(B_3|A_3) = 0.

Dakle, ako je voditelj izabrao vrata broj 2, po Bayesovoj formuli imamo:

Analogno dobijemo rješenje za B_3.

Vidimo kako je, ako voditelj otvori vrata broj 2, vjerojatnost da ćemo nagradu naći iza vrata 3, dvostruko veća od vjerojatnosti da ćemo je dobiti ako ostanemo pri starom izboru.

Originalna pitanja i odgovori iz časopisa Parade mogu se pročitati na web stranici Marilyn vos Savant.

Ovdje možete pogledati Javascript simulaciju paradoksa Montyja Halla.

Newcombov paradoks

Newcombov paradoks je misaoni pokus između dvaju igrača, od kojih jedan može predvidjeti budućnost. Paradoks je izmislio teorijski fizičar William Newcomb 1960., a popularizirao ga je Robert Nozick 1969. godine u filozofskom članku "Newcombov problem i dva principa izbora". Dok se o njemu puno raspravlja u filozofskoj grani teorije odluka, s matematičke strane nije dobio puno pozornosti.

Problem se zove paradoksom jer dvije strategije od kojih i jedna i druga zvuče intuitivno logično daju konfliktne odgovore na pitanje koji izbor maksimizira igračev dobitak.

Prva strategija tvrdi da, neovisno o predviđanju, uzimanje obiju kutija donosi više novca. To jest, ako je Predviđač predvidio da će igrač uzeti obje kutije, tada se odluka svodi na biranje između 1000$ i 0$, pa je očito korisnije uzeti dvije kutije. No, čak i ako je predviđeno da će igrač uzeti samo B, opet je bolje uzeti i A i B jer će tako dobiti 1 001 000$, dok bi uzimanje samo B donijelo samo 1 000 000$. Uzimanje i kutije A i B je bolje, neovisno o predviđanju.

Druga strategija predlaže uzimanje samo kutije B. Po ovoj strategiji možemo ignorirati mogućnosti koje vraćaju 0$ i 1 001 000$ jer one zahtijevaju da je Predviđač pogriješio, što se gotovo nikad ne događa. Došli smo do izbora između 1000$ (dvije kutije) i 1 000 000$ (kutije B) - dakle, bolje je uzeti kutiju B.

Ako je Predviđač 99% točan, tada je očekivana vrijednost uzimanja obiju kutija

Očekivana vrijednost za uzimanje kutije B je

Situaciju možemo i slikovitije zamisliti - u prilog prvoj teoriji, zamislimo da je kutija neprozirna samo s igračeve strane, a s druge strane netko neutralan gleda sadržaj. Jasno je da će se smijati igraču koji ne uzme dodatnih 1000$ koji su mu nadohvat ruke. S druge strane, možemo zamisliti i da je igra već više puta odigrana s drugim igračima. Svi koji su uzeli obje kutije dobili su 1000$, a svi koji su uzeli samo kutiju B dobili su 1 000 000$. Naravno da je bolje pridružiti se "klubu milijunaša" i uzeti kutiju B.

"Ovaj problem postavio sam velikom broju ljudi, i prijateljima i studentima na nastavi", piše Nozick u svom članku iz 1969. "Gotovo svima je savršeno jasno i očito što treba napraviti. Teškoća je u tome što su ti ljudi gotovo jednako podijeljeni na problemu, a veliki broj njih misli da je druga strana jednostavno budalasta."

Spomenimo i kako bi u slučaju da je u prvoj kutiji samo 1$ mnogi koji su podržavali ideju da treba uzeti dvije kutije, promijenili mišeljenje i uzeli samo drugu. Slično, ako sadržaj prve kutije povećamo na 900 000$, dio onih koji bi prije uzeli samo kutiju B, ipak će uzeti obje kutije, što nam govori da nitko od njih nije sasvim siguran koju strategiju izabrati.

Neki filozofi odbijaju se prikloniti bilo kojoj strani na temelju kritike da je nemoguće istodobno postojanje slobodne volje i bića koje će točno pogoditi izbor između dviju jednako razumnih akcija, pogotovo ako znamo da je izbor pogođen prije nego što ga napravimo.

Newcombov paradoks može se povezati i s pitanjem strojne svijesti, posebno ako savršena simulacija nečijeg mozga generira njegovu svijest. Pretpostavimo da je Predviđač stroj koji simulira mozak igrača koji je suočen s problemom biranja kutije. Ako simulacija generira svijest igrača, on ne zna stoji li ispred njega kutija u stvarnom svijetu ili u virtualnom svijetu simulacije. Tada će "virtualni" igrač reći Predviđaču koji izbor će napraviti "pravi" igrač.

Nozick je paradoks smatrao zgodnim problemom, te je napisao "Da je bar moj."

Russellov paradoks

Russelov paradoks još je jedan primjer koji nam pokazuje da Cantorova teorija skupova sadržava kontradikcije. Izmislio ga je Bertrand Russell (1872. – 1970.), britanski filozof, logičar, matematičar, povjesničar, sociolog, pacifist i društveni kritičar. Do otkrića je došao radeći na svojim Principles of Mathematics, gdje je diskusiji te kontradikcije posvetio cijelo poglavlje. Iako postoje dokazi da su drugi matematičari, među kojima su i Zermelo i Hilbert, bili već svjesni tog paradoksa, Russell je prvi detaljno opisao kontradikciju, pokušao formulirati rješenja i prvi je potpuno cijenio njegovu važnost.

Najpoznatija verzija paradoksa je priča o brijaču koju je sam Russell iskoristio kao ilustraciju problema.

Pretpostavimo da postoji grad i u njemu samo jedan muški brijač; te da su svi muškarci u gradu redovito obrijani. Neki se briju sami, a neki dolaze brijaču. Razumno je zamisliti sljedeće pravilo: Brijač brije sve i isključivo one muškarce koji se ne briju sami. U ovako zadanim uvjetima možemo postaviti pitanje: Brije li brijač sebe?

No, sad vidimo da je zadana situacija nemoguća.

• Ako se brijač ne brije sam, prema pravilu se mora obrijati, jer je on taj koji brije muškarce koji se sami ne briju.
• Ako se brije, prema pravilu, mora prestati, jer ne spada u skup ljudi koje smije brijati.

Iskažimo paradoks u jeziku teorije skupova.

Često se susrećemo sa skupovima koji nisu sami svoji članovi, naprimjer skup svih gradova u Europi, skup svih studenata matematike, skup svih cijelih brojeva. Ali, primjerice, skup svih skupova koji imaju više od jednog člana, sadržava sebe kao element jer je i sam skup s više članova.

Promotrimo sad skup svih skupova koji ne sadržavaju sebe kao element. Pitanje je - sadržava li taj skup sebe kao element?

Ako sadržava, tada nije ispunjen uvjet da sadržava sve skupove koji ne sadržavaju sebe kao element, no, ako ne sadržava, onda ne sadržava sve skupove koji ne sadržavaju sebe kao element jer ne sadržava samog sebe. Došli smo do kontradikcije.

Russell je paradoks otkrio 1901. i sam priznao da je tad pokušavao pronaći pogrešku u Cantorovu dokazu da ne postoji najveći kardinalni broj. Godine 1908. bila su predložena dva rješenja paradoksa - Russellova Teorija tipova i Zermelova Aksiomatska teorija skupova.

Literatura

• List of Paradoxes - Wikipedia, the free encyclopedia
• Cantor biography
• Russell's Paradox (Stanford Encyclopedia of Philosophy)
• Bertrand Russell - Wikipedia, the free encyclopedia
• Curry's paradox From Wikipedia, the free encyclopedia
• Curry's Paradox (Stanford Encyclopedia of Philosophy)
• Marilyn vos Savant | The Game Show problem
• Monty Hall problem - Wikipedia, the free encyclopedia
• The Monty Hall page
• Newcomb's paradox - Wikipedia, the free encyclopedia
• Newcomb's problem
• Robert Nozick and "Newcomb's Problem." - By Jim Holt - Slate Magazine
• Bertrand's paradox (probability) - Wikipedia, the free encyclopedia
• Dietrich Braess, Über ein Paradoxon aus der Verkehrsplanung
• The Braess Paradox
• Braess's paradox - Wikipedia, the free encyclopedia
• Gabriel's Horn - Wikipedia, the free encyclopedia
• Gabriel's Horn -- from Wolfram MathWorld
• Torricelli's Trumpet or Gabriel's Horn
• Koch snowflake - Wikipedia, the free encyclopedia

• Bryan Bunch, 1982. Mathematical Fallacies and Paradoxes, Dover Publications, Inc., Mineola, New York
• Eugene P. Northrop, 1944. Riddles in Mathematics A Book of Paradoxes, D. Van Nostrand Company, Inc., Princeton, New Jersey
• Michael Clark, 2002. Paradoxes from A to Z, Routledge, London

Kochova pahuljica

Kochova krivulja i Kochova pahuljica jedne su od prvih opisanih fraktalnih krivulja. Predstavio ju je švedski matematičar Niels Fabian Helge von Koch (1870. - 1924.) 1904. godine u radu “On a continuous curve without tangents, constructible from elementary geometry" (originalni francuski naslov: Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire).

To je jedan od najpoznatijih fraktala koji se često koristi kao reprezentativni primjer. Razlika između krivulje i pahuljice je u tome što se kod krivulje počinje s dužinom, a kod pahuljice s jednakostraničnim trokutom.

Možemo je nacrtati tako da počnemo od jednakostraničnog trokuta i rekurzivno mijenjamo svaku stranicu na sljedeći način:

1. Podijelimo dužinu na tri dužine jednake duljine.
2. Nacrtamo jednakostraničan trokut, tako da mu je osnovica srednja dužina dobivena u 1. koraku, a vrh gleda prema van
3. Uklonimo dužinu koja je osnovica trokuta iz 2. koraka

U Lindenmayerovu sustavu konstrukcija izgleda ovako:

• Početak: F + + F + + F
• Pravilo: F → F - F + + F - F
• Značenje:
  • F = "crtaj naprijed"
  • + = "zakreni u smjeru kazaljke na satu za 60°"
  • - = "zakreni u smjeru suprotnom od smjera kazaljke na satu za 60°"

Dakle,

• nulta iteracija: F + + F + + F
• prva iteracija: F - F + + F - F + + F - F + + F - F + + F - F + + F - F
• druga iteracija: F - F + + F - F - F - F + + F - F + + F - F + + F - F - F - F + + F - F + + F - F + + F - F - F - F + + F - F + + F - F + + F - F - F - F + + F - F + + F - F + + F - F - F - F + + F - F + + F - F + + F - F - F - F + + F – F …

Duljina

Recimo da je duljina početne dužine 1 m. Nakon prve iteracije, duljina krivulje je 4/3 m jer imamo četiri dužine duljine 1/3 m. Nakon druge iteracije, duljina je 16/9 m. Matematičkom indukcijom lako dolazimo do opće formule L = (4/3)ⁿ, n je broj iteracija. Vidimo da duljina raste eksponencijalno te zaključujemo da duljina teži u beskonačno, ako broj iteracija teži u beskonačno.

Površina

Budući da je duljina Kochove krivulje beskonačna (odnosno, teži u beskonačno), i duljina Kochove pahuljice je beskonačna. No, njena je površina konačna.

Uzmimo da je površina osnovnog trokuta 1. Jednostavnom podjelom trokuta vidimo da će manji trokuti u sljedećoj iteraciji imati devet puta manju površinu. Površina svih triju trokuta u prvoj iteraciji tada je 1/3 površine početnog trokuta. U sljedećoj iteraciji imamo 12 trokuta ukupne površine 4/27, a površina svih trokuta u sljedećoj iteraciji jest 16/243. Uočavamo da svi navedeni članovi osim prvog tvore geometrijski niz kvocijenta 4/9, čiji je zbroj:

Dodamo li još površinu početnog trokuta (koja nije dio geometrijskog niza), dobivamo ukupnu površinu \frac{8}{5} površine početnog trokuta.
 

Gabrielov rog

Gabrielov rog (ili Torricellijeva truba) je figura koju je otkrio Evangelista Torricelli, koja ima beskonačnu površinu, ali konačan volumen. Toricelli (1608. - 1647.) je bio talijanski fizičar i matematičar, najpoznatiji po svom izumu barometra. Paradoks je dobio ime po anđelu Gabrijelu koji svirajući trubu najavljuje Sudnji dan.

Gabrielov rog dobijemo tako da uzmemo graf funkcije y=\frac{1}{x} na domeni x \geq 1 i rotiramo ga u tri dimenzije oko x-osi. S pomoću integrala možemo odrediti volumen V i površinu A:

Iako a može biti proizvoljno velik, volumen nikad neće preći \pi, ali će se približavati \pi kad a teži u beskonačno:

Općenito, ako rotiramo krivulju y=f(x) za 2 π oko x-osi između granica x = a i y = b, površina dobivene figure je dana formulom

U slučaju Gabrielova roga imamo:

Površina će biti veća od 2\pi \ln a. Budući da \ln a nema gornju među kad a teži u beskonačno, rog će imati beskonačnu površinu:

U vrijeme kad je ovo otkriveno (prije otkrića integralnog računa) bilo je smatrano paradoksalnim. Torricellijev zaključak bazirao se na Cavalierievoj metodi uspoređivanja volumena područja među paralelnim ravninama.

Paradoksalna posljedica dobivenog rezultata je da Gabrielov rog možemo napuniti s π kubičnih jedinica boje, ali je beskonačan broj kvadratnih jedinica boje potreban za obojiti cijelu površinu. Jedno jednostavno rješenje je bojiti rog s unutarnje strane. Budući da stvarna boja ima volumen, rog će u jednom trenutku postati preuzak, pa će biti pokriven samo konačan dio površine.

Curryjev paradoks dobio je ime po američkom matematičaru Haskellu Brooksu Curryju, koji je osim po kombinatornoj logici poznat i po tome što su i dva programska jezika dobila po njemu ime – Haskell i Curry.

Curryjev paradoks

Ako je ova rečenica istinita, sve rečenice su istinite.

Curryjev paradoks pojavljuje se u naivnoj teoriji skupova i logici, a dopušta izvod proizvoljne rečenice iz rečenice koja se poziva na samu sebe.

Za primjer uzmimo rečenicu:

Ako je ova rečenica istinita, mačke znaju pričati.

Znaju li mačke pričati? Pa, ako je gornja rečenica istinita, onda znaju. Iako možda ne vjerujemo da mačke pričaju ili da je gornja rečenica istinita, možemo se složiti da je izjava - ako je ova rečenica istinita, onda mačke znaju pričati - istina.

No, onda gornja rečenica jest istinita, dakle, mačke znaju pričati. Nadalje, tvrdnju da mačke pričaju možemo zamijeniti bilo kojom tvrdnjom.

Kako bismo do zaključka došli formalno, označimo s X tvrdnju da Y slijedi iz istinitosti X. To možemo zapisati kao X = (X \to Y). Dokaz slijedi:

Do rezultata možemo doći i u naivnoj teoriji skupova. Neka je X = \lbrace x | (x \in x) \to Y \rbrace. Primijetimo da tada vrijedi: x \in X \Leftrightarrow ((x \in x) \to Y).

Na ovaj način, bilo koja tvrdnja, bez obzira je li točna ili nije, može biti dokazana. Matematička logika općenito ne dopušta rečenice koje se pozivaju na same sebe, no paradoks se pojavljuje u gotovo svim prirodnim jezicima. Rješenje Curryjeva paradoksa je trajni problem jer su rješenja (osim onih trivijalnih koja direktno ne dopuštaju X) komplicirana i neintuitivna. Logičari nisu odlučni oko toga jesu li takve rečenice nedopustive (i ako da, kako ih zabraniti), ili su beznačajne, ili su točne i otkrivaju probleme u samom konceptu istine (i ako da, treba li koncept istine odbaciti ili promijeniti).

Paradoks

Cantor je u svojoj teoriji sam otkrio paradoks koji je, iako ga nije objavio Cantor, postao poznat kao Cantorov paradoks.

Pokazali smo da za svaki skup partitivni skup sadržava više elemenata od početnog skupa. Vrijedi li to i za skup svih skupova? Budući da skup svih skupova sadržava sve skupove, svaki njegov podskup mora biti i njegov član. Dakle, skup svih skupova ne može imati više podskupova nego što ima članova.

Paradoks je izazvao razne pokušaje revizije teorije skupova ne bi li se zaobišao. U danas najviše prihvaćenoj, aksiomatskoj teoriji skupova paradoks nije moguć jer "skup svih skupova" nije legitimna definicija skupa.

Cantorov teorem

Za bilo koji skup A, partitivni skup od A ima strogo veći kardinalni broj od samog A.

Dokaz.

Promotrimo skup A. Postoji bar jedan skup podskupova od A iste kardinalnosti kao A. To može biti skup koji sadržava sve takve skupove da je u svakom od njih točno jedan element iz A. Naprimjer, za skup {1, 2, 3} to je skup {{1},{2},{3}}.

Neka je S partitivni skup od A.

Budući da pravila koja vrijede za konačne skupove ne moraju vrijediti za beskonačne, pretpostavimo da S ima isti kardinalni broj kao A. Pokazat ćemo da je postojanje bijekcije između A i S u kontradikciji s definicijom skupa S kao partitivnog skupa od A. Zasad pretpostavimo da su obje tvrdnje istinite.

Tada svakom elementu iz S možemo pridružiti jedan element iz A. Neka je Q neki element iz S, to jest, podskup od A. Skupu Q pridružili smo neki element iz A. Taj element može se i sam nalaziti u Q, ali i ne mora.

Primjer: Brojevi 3, 4 i 5 pridruženi su skupovima u kojima se sami ne nalaze.

Neka je a element iz A koji je pridružen nekom skupu iz S tako da se sam a ne nalazi u njemu pridruženom skupu. Neka je T skup svih takvih elemenata iz A. Skup T očito je podskup od A. No, tada po definiciji skupa S, skup T mora biti element od S, te mu zato mora biti pridružen neki element iz A, nazovimo ga t. Nalazi li se t u skupu T ili ne?

Primjer: Skupu koji sadržava sve brojeve koji su pridruženi skupovima u kojima se sami ne nalaze pridružili smo broj t

Po definiciji T, ako je t iz A pridružen skupu T, onda se sam ne smije nalaziti u T. Ali, ako t nije u T, onda sam mora biti element skupa kojem je pridružen. Došli smo do kontradikcije. Zaključujemo da ne postoji bijekcija između A i partitivnog skupa od A.