Zadanie
Medzitým jeho mladší brat Konštantín (odvodené od slova konštanta) dostal príležitosť vybrať si svoju nastávajúcu. Miestne krásavice sa nachádzali vo veži. Konštantínovi však padla do oka jedna, na samom vrchu veže.
Veža pokušenia má \(4\) poschodia. Prvé, druhé a tretie poschodie tvoria kocku \(3 \times 3 \times 3\) tak, že sa každé poschodie je tvorené \(9\) miestnosťami. Štvrté poschodie je tvorené len jednou miestnosťou uprostred, v ktorej čaká Konštantínova vyvolená. Do políčok druhého a tretieho poschodia veže diabol umiestnil dokopy najviac \(8\) dievčin tak, že žiadne dve nie sú v rovnakej miestnosti a na druhom poschodí žiadne dve nie sú ani v stenou susediacich miestnostiach.1 Konštantín je na prvom poschodí a snaží sa dostať k svojej vyvolenej tak, aby nestretol inú dievčinu.2 Konštantín sa vie pozrieť do ľubovolnej miestnosti, ktorá susedí vrcholom3, hranou alebo stenou s miestnosťou, kde sa práve nachádza, čím zistí, či v danej miestnosti je dievčina. Avšak takéto pozretie ho stojí \(1\) drahocenný Elixír bystrozrakosti. Okrem toho sa Konštantín vie (zadarmo) presunúť do ľubovolnej miestnosti, do ktorej sa dokáže aj pozrieť. Koľko najmenej Elixírov bystrozrakosti si musí Konštantín zobrať, aby sa s určitosťou vedel vyhnúť všetkým dievčinám a šťastlivo sa dostal k svojej vyvolenej?
Chceme ukázať \(2\) veci. Najprv chceme ukázať, že Konštantín potrebuje aspoň \(9\) elixírov bystrozrakosti a potom, že za použitia \(9\) elixírov sa už k svojej vyvolenej dostane.
Predpokladajme, že diabol rozmiestni všetky dievčiny do tretieho poschodia veže, to však Konštantín nevie. Nech si Konštantín zvolí ľubovoľnú stratégiu, musí vojsť do druhého poschodia. Ak si zvolí ľubovoľné políčko, musí použiť aspoň \(1\) elixír bystrozrakosti, lebo existuje rozdelenie dievčin, v ktorom na ňom je dievčina. Ďalej sa Konštantín bude musieť pozrieť do tretieho poschodia veže. Nech si zvolí ľubovoľné poradie políčok tretieho poschodia, existuje také rozdelenie dievčin, že bude musieť použiť \(8\) elixírov, kým zistí, že až na tom poslednom dievčina nie je. Potrebuje teda aspoň \(9\) elixírov.
Na \(9\) elixírov sa mu už podarí dostať k svojej vyvolenej. Najprv sa pozrie, za \(1\) elixír, do stredného políčka druhého poschodia.
Ak tam nie je dievčina, tak doň postúpi. Z tohoto políčka sa vie pozrieť na ľubovoľné políčko tretieho poschodia. Postupne sa na ne bude pozerať. V prípade, že do \(8\) pozretí narazí na políčko, kde nie je dievčina, tak naň môže postúpiť a z neho postúpiť na štvrté poschodie k svojej vyvolenej. V prípade, že sa pozrie \(8\)-krát a vždy uvidí dievčinu, tak sa mu podarilo nájsť dievčiny všetky a s kľudom v srdci môže postúpiť na posledné políčko tretieho poschodia, na ktoré sa nepozrel. Z neho postúpi na štvrté poschodie. Stálo ho to maximálne \(9\) elixírov.
V prípade, že v strednom políčku druhého poschodia bola dievčina, tak vieme, že na \(4\) susedných políčkach nie je. Medzi týmito políčkami teda vieme voľne chodiť. Nemusíme na to už používať žiaden elixír. Tieto políčka nám umožňujú sa pozrieť na všetky políčka tretieho poschodia. Konštantín sa na ne bude v ľubovoľnom poradí pozerať. Pokiaĺ počas prvých \(7\) pozretí narazí na políčko bez dievčiny, tak naň postúpi a z neho potom na štvrté poschodie. Pokiaľ nie, tak s kľudom môže postúpiť na ľubovoľné z ostávajúcich dvoch políčok, dievčiny už videl všetky a teda ani na jednom byť nemôže. V tomto prípade mu stačí iba \(8\) elixírov a o posledný sa môže podeliť so svojou vyvolenou. Spolu môžu z veže pozorovať obláčiky.
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ť.