Denník N

Hlavolamy! (1. diel, riešenia)

V predošlom blogu som zverejnil dve zaujímavé hádanky, jednu primerane ťažkú a jednu veľmi ťažkú. Je čas prezradiť si riešenia.

Ak ste minulý blog so zadaniami nepostrehli, nájdete ho tu. Zadania aj tak radšej zopakujem, poďme na to!


Dve vrecia

Máme dve vrecia, v prvom je 100 čiernych a 100 bielych gúľ, v druhom 200 bielych a 200 čiernych. S vrecami môžeme spraviť jediný experiment: vybrať z nich dve náhodné gule, pozrieť sa na ne a vrátiť ich obe späť. Experiment môžeme opakovať neobmedzene. Dokážeme na základe neho vrecia odlíšiť?

Riešenie:

Prvý krok, ako riešiť zložité úlohy, je zjednodušiť si ich. Čo ak by boli v prvom vreci len 1 biela a 1 čierna, v druhom dve a dve, čiže pomery ostanú zachované? Pri ťahaní z prvého vreca vždy vytiahnem dve rôzne gule, jednu bielu a jednu čiernu, viac ich tam predsa nie je. Pri ťahaní z druhé vreca niekedy vytiahnem dve rôzne gule, no nie vždy – občas budú rovnaké.

screen-shot-2016-12-03-at-13-19-11
Pri ťahaní z prvého vreca budú mať vždy obe gule rôznu farbu. Pri ťahaní z druhého tak bude len v 2/3 prípadov.

Keď vytiahnem prvú guľu, vo vreci ostávajú tri: jedna rovnaká a dve rôzne, mám teda 66.6% šancu, že vytiahnem opačnú farbu – čo sa v prípade prvého vreca dialo vždy.

Čo opačný extrém, vrece, kde je (takmer) nekonečno bielych a (takmer) nekonečno čiernych? Vytiahnem prvú bielu, no šanca vytiahnuť druhú bielu je stále 1:1, takže rôzne farby vytiahnem v 50% prípadov.

Ak sú vo vreci len 2 gule, vždy vytiahne rôzne. Ak ich je tam nekonečno, stane sa to len v polovici prípadov. Z toho už je jednoduché uvidieť, že čím je vo vreci viac gúľ, tým je väčšia pravdepodobnosť, že vytiahnem obe rovnaké.

screen-shot-2016-12-03-at-13-19-19
Čím viac gúľ je vo vreci, tým menej sa po vytiahnutí jednej z nich zmení pomer v nich. V prvom vreci je 16 gúľ, po vytiahnutí jednej bude pomer 7:8 (čiže 1:1.14), v druhom vreci je 32 gúľ po vytiahnutí jednej bude pomer 15:16 (čiže 1:1.06).

Takúto odpoveď napísal napríklad Vladimír Šatura „Vzdy budem vyberat gule len z jedneho vreca (je jedno z ktoreho). Prva gula je pomer 50:50, ta mi nic nepovie. Ale druhu vyberam zo zostavajucich cize uz bud z pomeru 199:200 alebo z 99:100. …“

Presne tak!


Mená v krabiciach

V miestnosti je 100 krabíc a v nich mená 100 väzňov (v každej jedno iné). Väzni stoja v rade a po jednom vchádzajú do miestnosti.  Keď je väzeň v miestnosti, musí v nej nájsť svoje meno, no môže otvoriť maximálne 50 krabíc. Keď s tým skončí, všetko vráti do pôvodného stavu a vyjde von bez toho aby komunikoval s ostatnými väzňami. Väzni si môžu dopredu dohodnúť stratégiu ako postupovať a budú ju potrebovať – ak čo i len jeden nenájde svoje meno,  všetkých popravia.

Vymyslite stratégiu, na základe ktorej väzni prežijú s pravdepodobnosťou aspoň 30%.

Riešenie: 

Znovu je lepšie začať zjednodušením, nech je väzňov len 10.

Prvý krok je taký, že väzni pomenujú krabice podľa svojich mien – čiže napríklad väzeň Adam povie, že prvé krabica sa volá po ňom – Adam. Daľší väzeň, napríklad Boris, pomenuje ďalšiu krabicu po sebe. Výsledok bude taký, že každá krabica má dohodnuté jedno meno (ktoré väzni poznajú) a vo svojom vnútri meno jedného väzňa (ktoré väzni nepoznajú). Pomenovanie krabíc môže byť úplne náhodné, ja som ich zoradil abecedne len kvôli prehľadnosti.

Situácia môže vyzerať napríklad takto:

screen-shot-2016-12-03-at-13-40-02
Čiernou je dohodnuté meno, šedou je tajné meno vnútri.

Stratégia každého z väzňov bude takáto – vojde dnu a otvorí krabicu so svojim menom. Pozrie sa, aké meno je v nej a otvorí krabicu s ním. Napríklad Adam otvorí 1. krabicu, potom 3., potom 6., potom 4. – a ďalej nemusí nič, tam sa už našiel.

screen-shot-2016-12-03-at-13-41-19
Adam postup pri otváraní krabíc. Napríklad Denis by postupoval veľmi podobne – prvý krok Adam a odtiaľ už rovnako, až k sebe.

Do obrázku som pridal aj šípku od Denisa k Adamovi. Hocikto z tejto štvorice si totiž prejde rovnaké kolečko (tzv. cyklus) – a každý z nich nájde svoje meno na 4. pokus (ich cyklus je dĺžky 4).

Čo Boris? Tesnotka, ale zvládne to. Dĺžka cyklu, v ktorom sa nachádza je 5, takže Boris, Emil, Gusto, Heňo aj Juro nájdu svoje meno na 5. pokus.

screen-shot-2016-12-03-at-13-43-54
Väzni nájdu svoje meno v cykloch dĺžky 1, 4 a 5. Všetci tak našli svoje meno na maximálne 5 pokusov.

Niekto si môže pomyslieť, že som to naschvál rozdelil tak, aby táto stratégia fungovala, ale nie – vyberal som náhodne a môj výber nebol nijak špeciálny. Ako to funguje? Náhodné pomenovania krabíc rozdelilo väzňov na tri skupinky:

  • Adam, Cecil, Filip, Denis,
  • Boris, Gusto, Hentrich, Juraj, Emil,
  • Ivan.

Iné (náhodné) pomenovania krabíc dopadne inak, napríklad

  • Adam, Boris,
  • Cyril, Juraj, Emil,
  • Denis, Henrich, Ivan,
  • Filip, Gusto.

Čo by fungovalo tiež: dvojice nájdu svoje meno na druhý pokus, trojice na tretí. Kedy to fungovať nebude? Ak ich jeden cyklus obsahuje aspoň 6

  • Boris, Gusto, Hentrich, Juraj, Emil, Ivan,
  • Adam, Cecil, Filip, Denis.

Borisovo meno sa ukrýva v krabici s menom Ivan, k nej sa ale dostane až na 6. pokus.

Väzni teda prežijú s pravdepodobnosťou, s akou náhodným pomenovaním krabíc nevznikne cyklus s dĺžkou aspoň 6 (resp. aspoň 51 v prípade 100 väzňov). Takéto je riešenie hádanky. Ak niekoho zaujíma pravdepodobnosť prežitia, nech sa páči  nastupuje (viac menej stredoškolská) matematika.


S akou pravdepodobnosťou dostaneme pri výbere 10 mien cyklus dĺžky 6?

Celkový počet možných pomenovaní je 10!. Možností ako vybrať 6 mien do cyklu je 10 nad 6, pričom každá z nich sa opakuje 4!*5! krát (toľko je možností pre pomenovanie zostávajúcich štyroch a poprehadzovanie 6 ľudí v cykle).

Dokopy je pravdepodobnosť vyrobiť cyklus dĺžky šesť (čiže počet takýchto pomenovaní deleno počet všetkých pomenovaní): 4! 5! Com(10,6)/10! = 1/6. Z toho je asi ľahké uvidieť, ako to dopadne pri cykly dĺžky 7, 8, 9, 10.

Pravdepodobnosť, že pri 10 väzňoch vznikne „smrteľný“ cyklus je teda 1/6 + 1/7 + 1/8 + 1/9 + 1/10 = 0.64 = 64%.

Pri sto väzňoch treba spočítať 1/51 + 1/52 + … + 1/100  = 68%.

Mimochodom, 1+1/2 + … + 1/k sa volá k-te Harmonické číslo, takže pre N väzňov sa dá pravdepodobnosť na prežitie napísať ako H(N) – H(1+N/2), čo sa v nekonečnej limite blíži k Logarimu z 2.


Dúfam, že sa vám prvý diel Hlavolamov páčil, určíte budú aj ďalšie.

Články a blogy nájdete na FB stránke Vedátor_sk

Zdroj obrázku

Teraz najčítanejšie

Samuel Kováčik

Absolvent teoretickej fyziky na Bratislavskom Matfyze, momentálne pôsobiaci na výskumnom inštitúte v Dubline.