Meie mõistatusülesanne eelmisel kuul oli päästa a Star Trek kaheksaliikmeline pinnapidu, mida juhib ettevõte Sideametnik Leitnant Uhura (mängis hiline Nicole Nichols). Meeskond on vangistatud tulnukate rassi Catenati poolt ühel planeedil riigis Kaelakee udukogu. Põgenemiseks peavad nad maksimeerima oma tõenäosust ülesande täitmisel, mis esialgu näib pakkuvat vaid nüri õnnestumise tõenäosust.
Kaheksaliikmelist meeskonda teavitatakse ülesandest, kui nad viibivad ajutiselt ühises ruumis, kus nad saavad vabalt suhelda ja strateegiaid koostada. Mõne tunni pärast viiakse nad ükshaaval ruumi, mida nimetatakse ruletikambriks. Selles ruumis on kaheksa järjestikku paigutatud nuppu, millest igaüks on programmeeritud reageerima erinevale meeskonnaliikmele. Meeskonna eksitamiseks märgistatakse iga nupp juhuslikult teise meeskonnaliikme nimega. Igal meeskonnaliikmel on lubatud vajutada kuni nelja nuppu mis tahes järjekorras. Iga kord, kui nad nuppu vajutavad, näevad nad, kellele see nupp tegelikult kuulub. Nelja katse jooksul peavad nad leidma neile määratud nupu. Et meeskond pääseks vabaks, peavad nad kõik selle ülesandega hakkama saama. Kui kasvõi üks neist ebaõnnestub, hukatakse kõik. Pärast seda, kui meeskonnaliige on katse lõpetanud, tuleb ta isoleerida, ilma et oleks võimalik oma meeskonnakaaslastele teavet edastada.
Eduvõimalused tunduvad väikesed. Kui meeskonnaliikmed valivad nupud juhuslikult, on igaühel võimalus oma nupp leida 1:2. Kõigi kaheksa õnnestumise võimalus on vaid 1:256 ehk umbes 0.4%.
Kuid nad ei pea nuppe juhuslikult vajutama. Üks võimalus edu tõenäosust suurendada võiks olla kõigi nupuvajutuste ühtlustamine mingil moel. See viib meid meie esimese mõistatusküsimuseni.
Mõistatus 1
Kui palju saab meeskonna ellujäämise tõenäosust parandada, kui nad veenduvad, et iga nuppu vajutatakse võrdselt (selle asemel, et vajutada suvaliselt nelja nuppu)?
Rob Corlett ja JPayette vastasid sellele hästi, nagu ka kõigile teistele küsimustele. Mis puudutab selle veeru mõistatuste tabamatut keskmist ideed, siis Rob Corlett, JPayette ja Jouni Seppänen kirjeldas seda ilusti, samas Sacha Bugnon aitas kaasa arvutilahendusele.
Siin on Rob Corletti vastus:
Üks võimalus tagada, et igale nupule vajutatakse võrdne arv kordi, on vangide jagamine kaheks võrdse suurusega 4-liikmeliseks rühmaks.
Iga rühm vajutab ainult oma rühma liikmetele vastavaid nuppe. Seega, kui A, B, C ja D on kõik samas alamrühmas, vajutage ainult A, B, C ja D nuppe.
See muudab probleemi nii, et küsitakse tõenäosust, et iga vang jaotatakse õigesse rühma, kuna siis on tagatud, et nad vajutavad nuppu nelja või vähema vajutusega.
Esimese rühma (ja seega ka teise grupi) nelja inimesega asustamiseks viiside arv on 4-st 8 valimise viiside arv, mis on C(8, 4) = 70. Seega Kõigi kahe rühma jagamine on 70.
On ainult üks jaotus, mis määrab iga kinnipeetava õigesti õigesse rühma ja seega on tõenäosus, et kõik kuuluvad õigesse rühma ja kõik vangid jäävad ellu, 1/70, mis on 3.66 korda parem kui eelmise strateegia 1/256. [Kuid see on siiski väga väike: vaid 1.4% tõenäosus.]
Mõistatus 2
Algset kurba koefitsienti on võimalik parandada üle 90-kordse, umbes 36.5%-ni, mis tundub imeline! See strateegia hõlmab oletusahelate või -ahelate kasutamist – sellest ka viited kaelakee udukogule ja Catenatile (catena on ladina keeles kett). Strateegia põhivormis alustab iga meeskonnaliige oma nime kandva nupu vajutamisega, seejärel jätkab nupuga, mis kannab selle meeskonnaliikme nime, kellele esimene nupp tegelikult kuulus, ja nii edasi, luues nimede ahela.
Vaatame, kuidas see praktikas töötab. Diagrammil on nupud näidatud valgete siltidega. Allolevad sinised tähed näitavad nuppude tegelikke omanikke. Kui esimene meeskonnaliige A siseneb ruletikambrisse, vajutab ta kõigepealt nuppu A. See on C nupp, nii et ta vajutab järgmisena nuppu C, seejärel nuppu E ja lõpuks nuppu F, mis on tegelikult A enda nupp, nii et ta on selle nelja katsega edukalt leidnud. Pange tähele, et nupud A-C-E-F moodustavad neljast nupust koosneva suletud ahela. Kui meeskonnaliikmed C, E ja F kordamööda käivad, läbivad nad ka sama suletud ringi, alustades oma vastavatest kohtadest ja leiavad nelja katsega ka oma nupud.
Sellel paigutusel on ka kaks väiksemat kahe nupuga silmust: B-D ja G-H. Need neli meeskonnaliiget leiavad oma nupud kahe katsega. Nii et selle korraldusega on kõik meeskonnaliikmed edukad ja nad on oma vabaduse teeninud. On selge, et kui korraldus sisaldab ainult 4 või lühema pikkusega silmuseid, on kõik meeskonnaliikmed edukad ja vabastatakse. Kui aga üks silmus on 5 või enam, ei leia kõik selle ahela meeskonnaliikmed nelja katsega oma nuppu ja meeskond hukatakse. Õnnestumise tõenäosuse leidmiseks võime leida tõenäosuse, et silmus on 5, 6, 7 või 8, liita need kokku ja lahutada selle summa 1-st. Seda on lihtsam arvutada kui teisiti, sest kaheksa puhul on nuppe, võib olla ainult üks 5, 6, 7 või 8 liikmeline silmus.
Neid on 8! erinevaid viise kaheksa nupu paigutamiseks. Kuid kui teeme silmuseid, moodustab sama tsükkel nendest paigutustest kaheksa (ABCDEFGH moodustab sama tsükli kui BCDEFGHA, mis on sama mis CDEFGHAB jne). Nii et tõenäosus, et silmus on suurusega 8, on (8!/8)/8!, mis on lihtsalt 1/8. Sarnaselt on 7. suuruse silmuse tõenäosus 1/7, 6 suuruse 1/6 ja 5 suuruse tõenäosus 1/5. Seetõttu on meie kartmatu meeskonna õnnestumise tõenäosus 1 − (1/5 + 1/6 + 1/7 + 1/8) ehk 36.5%, nagu varem mainitud.
Ülaltoodud strateegia töötab mis tahes arvu vangide puhul ja juhusliku lähenemise tõenäosus suureneb kiiresti, kui see arv suureneb. See on umbes seitsmekordne nelja vangi kohta, 24-kordne kuue, 93-kordne kaheksa ja hämmastav (3.8 × 1029)-fold 100 vangi kohta. Selle tohutu kasvu mõistmise võti seisneb selles, et meetod seob iga rühmaliikme edu või ebaõnnestumise teiste omadega. Väga suures osas õnnestuvad või ebaõnnestuvad nad kõik koos. Rühma õnnestumise tõenäosus ei lange liiga palju üksikisiku omast, langedes vaid 50%-lt üksikvangi puhul 30.69%-le, kuna vangide arvu suurendatakse piiramatult. Teisest küljest väheneb juhusliku lähenemise või isegi "paaris nupuvajutuse" lähenemise õnnestumise tõenäosus kiiresti isegi väikese arvu vangide puhul nulli lähedale.
Kui selle strateegia taga olev loogika tundub endiselt hägune, siis siin on 100 vangi probleemi analüüs. suurepärane video Veritasiumilt.
Mõistatus 3
See pusle rääkis sellest, et leitnant Uhura meenutas lapsepõlvemängu, mis oli sisuliselt sama pusle, aga kuuele inimesele. Vihjeks soovitasin nelja inimese jaoks probleemi lahendada. Nüüd, kui meil on valem, saame tõenäosused kergesti arvutada.
Nelja inimese puhul on tõenäosus, et pikim silmus on vaid 2 või 1: 1 − (1/3 + 1/4) ehk 41.7%, kusjuures juhusliku valiku puhul on see seitsmekordne.
Kuue inimese puhul on tõenäosus, et pikim silmus on 3, 2 või 1: 1 − (1/4 + 1/5 + 1/6) või 38.3% rohkem kui 24-kordse suurenemisega juhusliku valiku korral.
Mõistatus 4
Kui meie lugu jätkub, selgub, et üks Catenatitest on suhtunud sellesse erilise vastumeelsusega ettevõte meeskond ja jälgib neid eemalt. Ta kahtlustab, et nad on Uhura diagrammi põhjal välja mõelnud mõne tõhusa strateegia. Ta on otsustanud nende plaani nurjata, libisedes enne ruleti algust kambrisse ja muutes tahtlikult nuppude siltide järjekorda. Kas ta suudab plaani edukalt nurjata? Mida peab dessant eriti ettevaatlik olema, et varjata?
Meeskonna strateegiaarutelu alguses tõmbusid Uhura silmad ootamatult kitsaks. Ta andis oma meeskonnale märku ja hakkas rääkima nicholese keeles, teatades: "Palun kõik edasised arutelud nicholese keeles." Nikolai keel oli uus keel, mille Uhura oli oma karjääri alguses just selliste olukordade jaoks leiutanud, et vältida universaalsete tõlkijate kasutamist. "Oled kindlasti seda kahtlast Catenatit märganud," jätkas ta. "Ta võib proovida meid saboteerida, seega peame oma plaani muutma. Siin on, mida me peame tegema…”
Uhura visandas uut plaani, kuni oli veendunud, et iga tema meeskonnaliige teab seda suurepäraselt. Seejärel mõtiskles ta, pilk silmis: "Ma panin Nicholese'i nime ühe ikoonilise 20. sajandi näitlejanna järgi. Mul on hea meel, et nõudsin, et Tähelaevastik muudaks selle standardiks kõigil meie laevadel.
Ta pöördus tagasi meeskonna poole. „See on kõik, ohvitserid. Sa tead, mida teha!"
Me ei tea täpselt, mida Uhura oma meeskonnale ütles. Kuid JPayette'il ja Rob Corlettil oli päris hea idee. Siin on jälle Rob Corlett:
Kui kuri Catenati kuuleb, et nad kasutavad seda strateegiat, saab ta ekraanil kuvatavaid nimesid muuta, et tagada tsükli pikkus üle 4.
Selle katkestamiseks peavad vangid nõustuma salajase korraldusega, mis muudab järjestuse juhuslikuks. Nad teevad seda, öeldes midagi sellist: "Kui näete Uhura nime, siis minge nupule, millel on märge Chekov. Kui näete Tšekovi nime, minge nupule Smith jne.
Sel moel ei oma Catenati ümbertellimust tähtsust, kuna see toimib ainult siis, kui teate, kuidas meeskond ekraanil olevatele nimedele reageerib. Nad peavad siiski hoidma mis tahes ümbertellimise saladust, vastasel juhul võib see uuesti puruneda.
Nagu nägime, tagas Uhura, et saladust hoitakse turvaliselt. Iga meeskonnaliige pidi lihtsalt kasutama sama salajast käsku ja tagama, et kuri Catenati ei teaks, mis see on. Tegelikult suurendas kurja Catenati muudetud järjekord meeskonna õnnestumise tõenäosust!
Nii juhtus. Esimesena viidi ruletikambrisse Uhura. Ta vajutas kolme nuppu. Ükski polnud tema oma. Kas ta peaks olema kurb või rõõmus? Ta hoidis hinge kinni ja vajutas neljandat. Ta oli leidnud oma tõelise nupu!
Ta teadis, et nad kõik päästetakse.
Mõistatus 5
Millisele piirile läheneb maksimaalne õnnestumisprotsent, kui dessandi suurus kasvab lõputult? Kas saate selgitada, miks see meetod on palju tõhusam kui juhuslik nupuvajutus?
JPayette kirjutas:
Kõik ülaltoodud üldistatakse otsekohe kaheliikmelise meeskonna kohtan liikmed lubasid maksimaalselt vajutada n nupud. 2. mõistatusest järeldame, et nende eduvõimalus on suur
1 − (summa üle k vahel n + 1 ja 2n 1/k).
Seda summat saab võrrelda integraaliga 1/x üle intervalli [n, 2n], mis võimaldab meil tõestada, et as n kasvab lõpmatuseni, väheneb ülaltoodud tõenäosus, et läheneda hämmastavale väärtusele 1 − ln(2) ≈ 30.6%. [Tegelikult 30.69% kahe kümnendkoha täpsusega.]
Rob Corlett lisas:
Kui te integreerimist ei tea, saate kiiresti ligikaudse vastuseni arvutustabeli abil arvutades. Sain korra 0.307-ni n jõudis umbes 750-ni, mis on 3 kümnendkoha täpsusega.
Oleme juba eespool selgitanud, miks see meetod töötab. Kõiki silmuseid, mis on pikemad kui 1, jagavad mitu meeskonnaliiget. Seega on nende õnnestumised ja ebaõnnestumised omavahel tihedalt seotud. See on näide põhimõttest "Kõik ühe ja üks kõigi eest". Otse Starfleeti käsiraamatust välja!
Täname kõiki meie panustajaid. JPayette ja Rob Corlett esitasid mõlemad auhinnatud vastused, mis muutsid selle lahendusveeru peaaegu üleliigseks. Kahjuks pean ma kinni pidama meie reeglist, mille kohaselt tuleb iga mõistatuse veeru kohta valida üks võitja. Insightsi auhind läheb JPayette'ile, tunnustades siin ja eelmises mõistatuses tehtud panust. Palju õnne! Rob Corlett, teie panust ei unustata.
Kohtumiseni järgmisel kuul, et saada uusi teadmisi!
