2. Reťazce v Lemingove

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabovi na [email protected]

Zadanie možno vyzerá odstrašujúco dlhé. Je však jednoduchšie ako by sa mohlo zdať. Odporúčame ho riešiť úlohu po úlohe a veľa si kresliť. Už za nakreslenie niekoľkých obrázkov viete získať pomerne veľa bodov. Vaše kresby nám môžete odfotiť a vložiť do riešenia.

Poznáte lemingov zo známej počítačovej hry? Sú to malé postavičky, ktoré postupne vychádzajú zo svojho domčeka, idú neustále dopredu a snažia sa doraziť do cieľa. Niektorí z nich počas tejto cesty možno umrú, ale to až tak nevadí, lebo ich je skutočne veľa. Byť lemingom však vôbec nie je také ľahké, hlavne keď máte pred domom obrovskú dieru, ktorej sa vydáte v ústrety. Ak do nej spadnete, umriete.

V Lemingove je medzi štartovacím a cieľovým domčekom v rade niekoľko obrovitánskych (pre naše účely nekonečne hlbokých) dier, každá označená niektorým písmenom anglickej abecedy. Každú sekundu sa zo štartu vynorí nový leming, ktorý sa celý čas hýbe doprava a snaží sa dostať k cieľu.

Keď ste prišli na návštevu Lemingova s desom ste sa pozerali, ako sa každú sekundu vrhne ďalší leming do prvej diery. Nijakým spôsobom sa totiž cez ňu nevie dostať. V tomto okamihu hrôzy ste však v sebe objavili skryté magické schopnosti. Vysvitlo, že keď dostatočne nahlas poviete každú sekundu jediné písmeno, nad dierami označenými týmito písmenami sa na sekundu objaví most. Prechod cez most trvá lemingovi presne sekundu. To znamená, že leming stojaci na ľavom okraji jamy, nad ktorou sa objavil most, má akurát dosť času, aby sa dostal na jej druhú stranu.

Pozrite sa na obrázok nižšie. Na začiatku sekundy sa pri štarte objavil nový leming a vy ste zakričali písmeno B. Nad jamami s písmenom B sa objavil most. Cez prvú dieru vedie most, leming po ňom môže prejsť a dostať sa na druhú stranu. Následne všetky mosty zmiznú a zo štartu sa vynorí ďalší leming. V tomto momente ste však v nezávideniahodnej situácii, nech totiž poviete akékoľvek písmeno, nezachránite oboch lemingov. Môžete povedať písmeno B a zachrániť druhého leminga, alebo písmeno A a pomôcť prvému. Alebo budete zlí a poviete napríklad Z a oboch ich pošlete do jamy.

Úloha

1. (2 body) Nech v jamách sú postupne napísané písmená BABKA (ako na obrázku vyššie). Zo začiatočnej pozície, v ktorej je živý iba leming, ktorý práve vyšiel zo štartu, ste postupne povedali nasledovné písmená: BBABKAABABABKA – každú sekundu jedno v tomto poradí. Nakreslite, kde sa nachádzali lemingovia po tom, čo ste prečítali prvé štyri písmená, teda BBAB a po tom, čo ste prečítali prvých trinásť písmen, teda BBABKAABABABK.

   Popri tom, ako ste vraveli text BBABKAABABABKA ste si pozorne všímali, kde sa nachádzajú lemingovia. Zaujímalo vás totiž koľkokrát sa v tomto texte vyskytlo slovo BABKA, ktoré je tvorené písmenami z jám. Ako vám vie poloha lemingov prezradiť, že v hovorenom texte sa nachádza slovo z jám? Prečo je tomu tak?

2. (2 bod) Hľadanie slov v texte sa vám zapáčilo a povedali ste si, že by to mohlo byť aj pomerne užitočné. Pozor však, že hľadané písmená sa v texte musia nachádzať za sebou. V texte BAZBKA sa teda slovo BABKA nenachádza ani raz.

   Vymyslite text dlhý 15 písmen, v ktorom sa slovo KATKA nachádza čo najviackrát.

3. (4 body) Keď ste sa vrátili z Lemingova, po rozume vám stále behal ich zvláštny spôsob života. Začali ste si teda kresliť na papier, akoby sa lemingovia pohybovali pri rôznych písmenách v jamách a textoch, ktoré by ste čítali. Prekresľovať zakaždým všetkých lemingov je ale strašne otravné. Radšej by ste sa sústredili iba na jedného – toho čo je najviac vpravo a teda najbližšie k cieľu. Posúvať jedného leminga je totiž oveľa jednoduchšie. Keď však tento leming prišiel do cieľa a zmizol v domčeku, zrazu ste nevedli, kde sú ostatní lemingovia. Možno to viete spätne vypočítať.

   Predstavte si, že poznáte písmená v jamách a pozíciu najpravejšieho leminga, ktorý ešte nevošiel do cieľového domčeka. Vedeli by ste zistiť, kde sa nachádzajú ostatní lemingovia? Viete o každom mieste naľavo od neho povedať, či sa tam leming nachádza alebo nie? Je toto umiestnenie jednoznačné? Odôvodnite svoje tvrdenia v popise. Takisto do popisu napíšte postup, ktorým by ste zisťovali pozície zvyšných lemingov.

   Aby ste lepšie pochopili, čo v tejto úlohe treba robiť, skúste si ju vyriešiť na konkrétnom príklade z obrázku nižšie. Za správne určenie pozícií lemingov v tomto obrázku môžete získať až 2 body.

4. (4 body) Povedať niečo o lemingoch keď poznáte písmenká v jame je ľahké, čo však, keď neviete ani to? Predstavte si, že medzi štartom a cieľom je 17 jám a nepoznáte písmená, ktoré im prislúchajú. Medzi jamami sa nachádzajú nejaký lemingovia. Vy ste si všimli jedného, ktorý práve dorazil na koniec slova a chystá sa vstúpiť do domčeka s cieľom. K nemu najbližšie stojí leming za 12-tou jamou, medzi nimi žiaden ďalší leming nie je. Rozhodnite a svoje tvrdenie odôvodnite, či za siedmou a jedenástou jamou stojí leming.

5. (3 body) Počas toho ako ste sa hrali s rôznymi slovami sa vám najviac zapáčili také, v ktorých sa pravidelne opakovala nejaká postupnosť písmen, mali takzvanú periódu. Slovo je periodické práve vtedy, ak vzniklo opakovaním tej istej postupnosti písmen. Napríklad periodické slovo MAMA vzniklo opakovaním postupnosti MA. Slovo ABABABABABAB mohlo vzniknúť aj opakovaním štyroch písmen ABAB aj opakovaním dvoch písmen AB. V takomto prípade nás však zaujíma najkratšia možná perióda.

   Presnejšie, slovo má periódu \(p\), ak platí, že ľubovoľné dve písmená, ktoré sú od seba vo vzdialenosti \(p\), sú rovnaké. Slovo ABABABAB má preto periódu 2, slovo PAAPPAAPPAAP má periódu 4 a slovo LLLLLLL má periódu 1. Dokonca, mierne prekvapivo, napríklad slovo KATKA má periódu 3 – naozaj platí, že písmená vo vzdialenosti tri sú v ňom rovnaké. Ako ďalšie príklady si môžeme ukázať slovo KATKAKAK s periódou 7 a slovo MACKA s periódou 5.

   Zaujíma vás, či vám vedia lemingovia pomôcť s určovaním periódy. Do jám ste teda napísali písmená slova, ktorého periodickosť chcete zistiť. Následne ste postupne čítali písmená tohto slova a sledovali, ako sa hýbu lemingovia. Keď ste skončili, pri cieľovom domčeku určite stál leming a ďalší boli možno niekde po ceste. Viete na základe tohto zistiť, akú periódu má zadané slovo? Svoje tvrdenia odôvodnite. Snažte, aby bolo vaše riešenie všeobecné a fungovalo na ľubovoľnom slove.