Zadanie

František zobral Krtka do audienčnej siene, kde mala Mária Terézia práve poradu. Avšak miesto radenia sa o problémoch krajiny jej radcovia naháňali jej 7 detí po celej sále. Nešťastná pestúnka len zalamovala rukami a snažila sa stiahnuť posledné dieťa z rokovacieho stola. Potom, čo František s Krtkom vošli, cisárovná Mária Terézia ukázala prstom na Krtka a spýtala sa: „To je tá nová pestúnka?“ Keďže nečakala na odpoveď, Krtkovi nezostalo nič iné než začať chytať deti. Naraz dostal vynikajúci nápad. Z tašky vytiahol pravidelný osemsten a zapískal. Deti zaujaté neznámym predmetom sa okolo neho zhŕkli a Krtko sa pustil do vysvetľovania svojej hry.

Čísla \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\) náhodne napíšeme na steny pravidelného osemstena, každé práve raz, na každú stenu práve jedno číslo. Aká je pravdepodobnosť, že žiadne dve za sebou idúce čísla nie sú napísané na stenách, ktoré majú spoločnú hranu? Čísla \(1\) a \(8\) považujeme tiež za za sebou idúce.

Pravdepodobnosť spočítame tak, že vypočítame pomer počtu vyhovujúcich označení stien osemstena k počtu všetkých možných označení osemstena. Všetkých označení je \(8!\), pretože pre prvé číslo máme \(8\) možných stien, pre ďalšie už len \(7\) voľných stien, a tak ďalej.1

Poďme spočítať, koľko je vyhovujúcich očíslovaní stien. Ofarbime si steny nášho osemstena striedavo čiernou a bielou tak, že čierna stena susedí iba s bielymi stenami a biela iba s čiernymi. Je celkom ľahko vidno, že takéto ofarbenie existuje. Toto ofarbenie má tú peknú vlastnosť, že ak po sebe idúce čísla sú na stenách tej istej farby, tak určite nie sú na susedných stenách a všetko je v poriadku. Naopak, ak by mali byť nejaké dve po sebe idúce čísla na stenách rôznych farieb, musia to byť steny presne oproti sebe (voči stredu osemstenu). Steny oproti sebe sú zas vždy rôznych farieb.

Namiesto toho, aby sme priamo priraďovali k číslam \(1\) až \(8\) steny osemstena, najskôr k nim priradíme iba farby stien a až potom priradíme ku každému číslu niektorú zo stien priradenej farby. Počet očíslovaní stien teda zistíme takto v dvoch krokoch.

Keď si zapíšeme farby stien, na ktorých sú čísla \(1\) až \(8\), postupne do kruhu (pretože aj \(1\) a \(8\) sú za sebou idúce čísla), dostaneme kruhový zoznam. Ten sa skladá z nejakých úsekov rovnakých farieb, na ktoré sa pozrieme bližšie.

Prvé pozorovanie je, že ak je číslo \(i\) na bielej stene a číslo \(i+1\) na čiernej, \(i+2\) nemôže byť na bielej (pretože by muselo byť na stene oproti \(i+1\), aby s ním nesusedilo, ale tam už je \(i\) z rovnakého dôvodu). Samozrejme, počítame tu modulo2 \(8\). Inak povedané, každý úsek jednej farby má dĺžku aspoň dva. Ďalej platí, že biele úseky a čierne úseky sa na kruhu striedajú, teda oboch je rovnako veľa.

Rozoberme si (disjunktné3) prípady, ktoré môžu nastať:

1. prípad

Ak máme iba jeden čierny a jeden biely úsek, oba úseky musia mať dĺžku \(4\) (máme \(4\) biele a \(4\) čierne steny). Máme \(8\) možností pre číslo, kde začína čierny úsek (\(8\) možných rotácii). Čierne steny môžeme medzi čísla rozhodiť \(4!\) spôsobmi, pretože všetky priradenia čiernych stien k štyrom po sebe idúcim číslam sú vyhovujúce. Dve biele steny, ktoré majú číslo o \(1\) menšie a číslo o \(1\) väčšie ako čísla na kraji úseku čiernych stien, sú určené jednoznačne, zvyšné dve vieme priradiť dvomi spôsobmi.

Príklad: Čísla \(4\) až \(7\) sú na čiernych stenách. To, ktoré je na ktorej z čiernych stien, si vieme ľubovoľne zvoliť. \(3\) musí byť na bielej stene oproti \(4\) a \(8\) na bielej stene oproti \(7\). \(1\) a \(2\) môžu byť na zvyšných bielych stenách ľubovoľne.

Dokopy teda máme \(8 \cdot 4! \cdot 2 = 16 \cdot 4!\) možností.

2. prípad

Ak máme dva čierne a dva biele úseky, musia mať všetky dĺžku práve \(2\), ak by boli dlhšie, dokopy by mali dĺžku viac ako \(8\), čo nemôže nastať. Máme \(4\) možnosti (rotácie) na výber, ktoré čísla budú na čiernych stenách – štvorice \((1,2,5,6)\), \((2,3,6,7)\), \((3,4,7,8)\) a \((4,5,8,1)\). Keď si toto zafixujeme, čierne steny môžeme týmto štyrom číslam priradiť ľubovoľne \(4!\) spôsobmi, pretože žiadne dve nesusedia. Každé číslo na bielej stene má o jeden väčšie alebo menšie číslo na čiernej stene, oproti ktorému sa musí nachádzať. Každé číslo má túto svoju dvojičku inú, ale jednoznačne určenú. Naozaj sme teda mohli čierne steny priradiť ľubovoľne, biele sa budú tiež dať priradiť, a to práve jedným spôsobom.

Príklad: Čísla \(2\), \(3\), \(6\) a \(7\) sú na čiernych stenách, \(4\), \(5\), \(8\) a \(1\) na bielych. Ktoré číslo je na ktorej čiernej stene, si vieme zvoliť ľubovoľne, potom \(4\) musí byť na stene oproti \(3\), \(5\) na stene oproti \(6\), \(8\) oproti \(7\) a \(1\) oproti \(2\). Pre biele je iba jedna možnosť.

Dokopy máme \(4 \cdot 4!\) možností.

Záver

Viac jednofarebných úsekov mať nemôžeme, takže sme napočítali dohromady \(16 \cdot 4! + 4 \cdot 4! = 20 \cdot 4!\) možností z \(8!\), celková pravdepodobnosť je teda \[\frac{20 \cdot 4!}{8!} = \frac{20}{8 \cdot 7 \cdot 6 \cdot 5} = \frac{1}{2 \cdot 7 \cdot 6} = \frac{1}{84}.\]

  1. Výkričník značí operáciu faktoriálu, ktorá je definovaná tak, že \(n!\) je súčin všetkých prirodzených čísiel od \(1\) do \(n\), teda napríklad \(8! = 8 \cdot 7 \cdot 6 \cdot \dots \cdot 1\).↩

  2. Ak napríklad \(i=8\), tak \(i+1\) berieme, že je \(1\), nie \(9\). Po osmičke nám nasleduje číslo \(1\). Na rozdiel od obvyklého modulovania – počítania so zvyškami tu však nemáme číslo \(0\), ale \(8\).↩

  3. Žiadne dva prípady sa neprekrývajú.↩

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.