2. Pavúčí sklad

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

Pavúk Jonáš nie je ako zvyšné pavúky. Rád programuje, je poriadkumilovný a tká vskutku nezvyčajné siete, do ktorých si potom ukladá potravu. To mu však občas dosť komplikuje život. Navigovať sa v jeho sieťach nie je vôbec jednoduché a odkedy si robil zásoby na zimu, stratil prehľad o všetkých chytených muškách. Našťastie pri stavaní siete dodržiaval niekoľko prísnych pravidiel, a preto sa v nej určite bude dať nájsť nejaký systém. Pomôžete mu s tým?

Na obrázku môžete vidieť jeden možný príklad siete pavúka Jonáša. Teraz vám povieme, aké pravidlá Jonáš dodržiava pri stavaní siete. Môžete si teda overiť, že aj táto sieť spĺňa dané pravidlá.

V sieti sa nachádza niekoľko mušiek, ktoré Jonáš chytil a zviazal do pavučiny. Každá z týchto mušiek má rôznu váhu reprezentovanú jedným celým číslom. Zvyšok pavučiny tvoria vlákna naťahané medzi týmito muškami. Na samom vrchu pri Jonášovi je prvá muška, ktorú chytil – muška Miška. Z mušky Mišky vedú dodola najviac dve vlákna, jedno vedie doľava a druhé doprava. Naviac musí platiť, že všetky mušky, ktoré sú na ľavej strane sú ľahšie ako Miška a všetky mušky, ktoré sú napravo sú ťažšie ako Miška.

Táto vlastnosť však neplatí iba pre mušku Mišku, ale pre všetky mušky v sieti. Teda nech si zoberieme ľubovoľnú mušku, tak z nej dodola vedú najviac dve vlákna (niekedy len jedno ako pri muške 35 a niekedy dokonca žiadne ako pri muške 24) a všetky mušky, ktoré sú pod ňou na ľavej strane sú ľahšie ako ona a všetky mušky, ktoré sú pod ňou na pravej strane sú ťažšie ako ona.

Na obrázku si môžete skontrolovať, že to naozaj tak je. Ak si zoberieme mušku 29, tak naľavo pod ňou sú mušky 3, 15 a 24, ktoré sú všetky ľahšie a napravo pod ňou sú mušky 35 a 30, ktoré sú ťažšie.

Jonáš sa po sieti môže pohybovať iba po naťahaných vláknach. Napríklad ak by sa chcel dostať k muške 30, musel by najskôr zliezť k muške 29, potom k muške 35 a až potom by sa vedel dostať k muške 30. Pri tom by zliezol po troch vláknach.

Úloha

Táto úloha sa skladá z niekoľkých podúloh. V každej z nich je vašou úlohou prísť s postupom, ktorý pomôže Jonášovi dosiahnuť jeho cieľ. Tento postup by mal byť všeobecný a mal by fungovať na ľubovolnej sieti, ktorá spĺňa podmienky zadania. K dispozícii máte tri obrázky rôznych sietí. Overte si, či váš postup funguje na každej z nich. A možno si nakreslite aj ďalší obrázok, ktorý bude vyzerať ešte inak a bude obsahovať iné čísla a overte si to aj na ňom.

Ku každej podúlohe, ktorú vyriešite, napíšte postup, ktorým sa má Jonáš riadiť. Takisto popíšte, prečo tento postup funguje pri ľubovoľnej sieti a môžete tiež ukázať, ako sa tento postup dá použiť na jednom z obrázkov zo zadania.

1. (2 body) Jonáš stojí na vrchu siete pri muške Miške. Chcel by zjesť najmenšiu mušku, ktorú má v sieti chytenú. Navrhnite postup, ktorým sa dostane k najľahšej muške. Snažte sa, aby pri tom musel zliezť po čo najmenej vláknach.

   Pri sieti z prvého obrázka by teda Jonáš mal nájsť mušku s váhou 3. Nezabudnite zdôvodniť, prečo váš postup naozaj nájde vždy tú najľahšiu mušku.

2. (2 body) Jonáš stojí pri muške Miške. Chcel by nájsť najľahšiu mušku, ktorá je ťažšia ako muška Miška. Viete mu pomôcť navrhnúť postup, ktorým takúto mušku nájde?

   V prvej sieti, v ktorej má muška Miška váhu 42, by teda mal nájsť mušku s váhou 47.

3. (3 body) V tejto podúlohe by chcel Jonáš zjesť mušku s veľmi konkrétnou váhou. Jonáš vám túto váhu zadá, označme si ju \(x\). Vymyslite postup, ktorým Jonáš nájde mušku s váhou \(x\) (pre ľubovoľné \(x\), ktoré vám Jonáš povie), alebo zistí, že taká muška v sieti nie je. Opäť sa snažte, aby sa Jonáš čo najmenej nachodil. Aj v tejto úlohe Jonáš začína na vrchu siete.

   Ak by teda v prvej sieti chcel zjesť mušku s váhou 30, váš postup by mal nájsť cestu po troch vláknach cez mušky 29 a 35. Ak by ale hľadal mušku s váhou 50, váš postup by mal zistiť, že taká muška tam nie je. Aj pri tom môže Jonáš chodiť po sieti.

4. (4 body) Jonášovi sa pri dnešnom love darilo a chytil mušku s váhou \(x\). Víťazoslávne ju teraz drží na vrchu siete. Chcel by si ju však niekde zavesiť. To však nemôže spraviť len tak. Chce aby výsledná sieť naďalej spĺňala všetky podmienky zo zadania. A naviac, nechce pretrhávať žiadne už existujúce vlákna. Novú mušku preto môže zavesiť iba pod mušku, z ktorej nevedie naľavo alebo napravo vlákno. Nájdite riešenie, pri ktorom sa Jonáš čo najmenej nachodí.

   Napríklad ak by ulovil mušku s váhou 58, mohol by ju zavesiť napravo od mušky 55. Nemohol by ju však zavesiť pod mušku 3 (či už vľavo alebo vpravo), lebo takéto zavesenie by porušilo jednu zo základných podmienok – naľavo od mušky 15 by bola ťažšia muška 58. Takisto túto mušku nemôže zavesiť pod mušku 29, keďže tá už má mušku naľavo aj napravo od seba. Všimnite si, že toto platí rovnako pre prvý aj druhý obrázok.

   Ak by Jonáš ulovil mušku s váhou 1, správne zavesenie na týchto obrázkoch by bolo naľavo od mušky 3.

5. (4 body) Jonáš zjedol jednu z mušiek a teraz stojí na jej mieste. Ak by však na toto miesto nedal žiadnu inú mušku, sieť sa mu pravdepodobne pokazí. Chcel by preto previazať niektoré vlákna tak, aby opäť dostal sieť, ktorá vyhovuje jeho podmienkam. Pomôžte mu nájsť postup, ktorým také niečo vie spraviť. Snažte sa, aby pri vašom postupe musel preväzovať čo najmenej vlákien.

   Pozrieme sa na prvú sieť z druhého obrázku. Ak Jonáš zje mušku s číslom 24, vlastne nemusí nič robiť, sieť spĺňa zadané pravidlá. Pri zjedení mušky 55 by to bolo o niečo ťažšie, stále by to však vedel pomerne rýchlo previazať. Ak by však zjedol napríklad mušku 29, situácia by bola výrazne ťažšia.