Zadanie

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

“Slnko, teplo, horúci kameň… Ach, čo môžu byť lepšie podmienky na to, aby som sa rozvalil na jeden z týchto kameňov, vyhrieval sa a trávil obed zjedený pred troma dňami? Ale nemôžem sa zvaliť hocijako, musí to pekne vyzerať…”

Pytón Peťko sa veľmi rád vyhrieva na slnku a ešte radšej sa zvíja do takých polôh, aby jeho telo tvorilo nejaký pekný obrázok či vzor. Naposledy sa zvinul do tvaru domu a vyzeralo to ako na prvom (ľavom) obrázku nižšie.

Tvar tela sa mu síce páčil ale veľmi zle sa mu trávil obed. Na dvoch miestach totiž ležal krížom cez seba, čo je nielen nepohodlné ale aj nebeznepečné, lebo hrozilo, že sa upchá, nafúkne sa a praskne. Na druhom obrázku sú citoslovcami “AU!” označené miesta, ktoré treba opraviť. Miesta označené “OK”, sú v poriadku, lebo tam leží had len tesne vedľa seba, nie krížom cez seba. Skúste pytónovi poradiť, ako si má ľahnúť, aby neležal krížom cez seba.

Keď ste Peťkovi poradili, ako si má ľahnúť, vymyslel si tri ďalšie obrázky, ktoré by chcel zo svojho tela vymodelovať tak, aby sa neupchal. Tento raz sa však kusol do chvosta a preto hada kreslite tak, aby začínal a končil na tom istom mieste.

Úloha

  1. (2 bod) Nakreslite obrázok domčeka jedným ťahom tak, aby sa vaša čiara na žiadnom mieste neprekrížila. Obrázok nemusí byť pekný, ale musí na ňom byť vidno, ako vedie had. (Môžete napríklad očíslovať kúsky hada od hlavy po chvost.)

  2. (7 bodov) Vyplňte krúžky v nasledovných troch obrázkoch tak, aby bol celý obrázok tvorený jednou čiarou, ktorá sa nikde nekrižuje. Samozrejme, po každej nakreslenej čiare môžete ísť len raz. Pokiaľ sa nejaký z obrázkov nedá nakresliť takýmto spôsobom, pokúste sa napísať, prečo sa to nedá.

    Kreslite tak, aby bolo jasne vidieť, čo je s čím spojené. Napríklad ako na prvom obrázku. Samorejme ukážkový obrázok vyplneného kvetu nie je správny pretože čiara sa na dvoch miestach križuje a navyše to nie je jeden had ale dva hady.

  1. (6 bodov) Pytón Peťko si všimol, že každý obrázok, ktorý vie vymodelovať svojím telom, vie vymodelovať aj tak, aby na žiadnom mieste neležal cez seba. Nevie však vymyslieť, ako to má spraviť. Predstavte si, že ste dostali obrázok nakreslený jednou čiarou, ktorá mohla sama seba prekrížiť. Navrhnite spôsob, ako takýto obrázok nakresliť znova alebo opraviť už nakreslený obrázok, aby sa čiara nekrižovala (aby sa pytón nepriľahol). Môžte si to predstaviť tak, že máte niekoľko krúžkov, v ktorých sa čiary stretnú (ako v obrázkoch z predošlej podúlohy) a chcete navrhnúť postup, ako tieto krúžky prekresliť, aby celý obrázok tvorila jedna nepretínajúca sa čiara. Pre jednoduchosť môžete predpokladať, že do každého krúžka vchádzajú práve 4 čiary.

Podúloha a)

Existuje niekoľko správnych riešení tejto úlohy, jedno z nich vyzerá napríklad takto:

Stačilo si uvedomiť, že had môže zahnúť aj v strede domčeka a potom sa to už riešilo samo.

Podúloha b)

Prvé dva obrázky sa dali nakresliť a to nasledovne:

Druhý obrázok je pre lepšiu zrozumiteľnosť nakreslený hranatý. Na nájdenie riešenia sa stačilo trochu pohrať s obrázkami.

Tretí obrázok sa nielenže nedal nakresliť tak, aby sa had neprekrýval, ale dokonca sa ani nedal nakresliť jednou čiarou.

Čo sa deje, ak obrázok kreslíme jedným ťahom? Zoberme si takúto čiaru a prejdime po nej prstom. Vždy, keď prstom vojdeme do nejakej križovatky (krúžku), poznačíme si ku križovatke modrú bodku a vždy keď vychádzame z krúžku, poznačíme si červenú bodku. Pokiaľ je čiara uzavretá (had sa zakusol do svojho chvosta), tak vždy, keď do nejakej križovatky vojdeme, tak z nej aj musíme výjsť. S výnimkou krúžku, kde začíname. Tam najskôr výjdeme von, ale na konci sa tam zase vrátime. Tým pádom, pri každej križovatke máme rovnako veľa modrých a červených bodiek. Celkový počet bodiek pri každej križovatke je preto párny.

Uvedomme si, že pri každej križovatke máme po nakreslení cesty pre hada presne toľko bodiek, koľko z nej trčí čiar. Preto na to, aby sme vedeli nakresliť trasu hada, z každej križovatky musí trčať párny počet čiar. Na našom obrázku sú 4 križovatky, z ktorých trčia 3 čiary, a preto sa obrázok nedá nakresliť jednou uzavretou čiarou.

Ešte dodám, že v prípade, že by čiara nebola uzavretá, teda by mohla začínať na inom mieste ako končiť, tak by sme mohli mať dve križovatky, z ktorých by trčal nepárny počet čiar (keď v križovatke začíname, tak máme o 1 červenú bodku viac, keď v križovatke končíme, tak je tam o 1 modrú bodku viac). Náš obrázok má 4 križovatky s nepárnym počtom čiar, takže sa nedá nakresliť ani neuzavretou čiarou.

Podúloha c)

Chceme ukázať, že keď dostaneme hocijaký obrázok nakreslený jednou čiarou, tak ho vieme prekresliť tak, aby sa čiara nikde nepretínala.

Ukážeme si dve rôzne riešenia tejto úlohy. Prvé je jednoduchšie a predpokladá, že v každej križovatke sa stretávajú práve štyri čiary. V druhom riešení môžu do križovatiek vchádzať akékoľvek množstvo čiar, ale toto riešenie je trocha komplikovanejšie.

Prvé riešenie

Na začiatku máme obrázok nakreslený jednou čiarou. Pokiaľ sa táto čiara nikde nepretína, tak máme to čo sme chceli a môžeme skončiť. Pokiaľ má čiara nejaký priesečník (križovatku kde sa had kríži cez seba), môžeme ho odstrániť nasledovným spôsobom:

Pozrieme sa na celú čiaru ako na hada a prejdime prstom od hlavy až ku chvostu. Čiaru, ktorou sme prvýkrat vošli do priesečníka označíme \(a\), čiarou ktorou sme následne vyšli von označíme \(b\), čiaru ktorou sme druhýkrat vošli do tejto križovatky označíme \(c\) a čiaru, ktorou sme nakoniec vyšli von označíme \(d\). (Keďže má križovatka stupeň 4, musíme dvakrát vojsť a dvakrát vyjsť von).

Jediné, čo potrebujeme spraviť je hada prekresliť tak, aby nešiel z \(a\) do \(b\) a z \(c\) do \(d\), ale namiesto toho z \(a\) do \(c\) a z \(b\) do \(d\). Takto dostaneme rovnaký obrázok, ktorý bude naďalej tvorený jednou čiarou, ale bude mať o jeden priesečník menej.

Prekreslenie jedného priesečníka je znázornené na obrázku.

Pokiaľa má celá čiara viacero priesečníkov, jednoducho ich postupne po jednom odstránime práve predvedeným spôsobom. Napokon dostaneme jednu nepretínajúcu sa čiaru.

Druhé riešenie

Obrázok vyrobíme v dvoch krokoch.

V prvom kroku nakreslíme obrázok tak, aby sa nepretínal, ale dovolíme, aby bol tvorený viacerými čiarami (čiže môžeme mať viacero hadov, ktoré dokopy tvoria daný obrázok). Všetky čiary budú cyklické – nebudú mať začiatok ani koniec (ako keby sme nakreslili viac hadov, ktorí si zahryzli do chvosta). Takýto obrázok vytvoríme veľmi jednoducho. V každej križovatke sa pozrieme na všetky čiary, ktoré z križovatky trčia a tieto trčiace čiary pospájame ľubovoľným spôsobom, tak aby sa nepretínali. Napríklad môžeme zoradiť čiary do kruhu v smere hodinových ručičiek a spojiť prvú s druhou, tretiu so štvrtou atď.

Na obrázku môžeme vidieť zväčšenú križovatku, z ktorej trčí osem čiar. Modrou farbou je znázornené, ktoré trčiace čiary sú spojené. Vyobrazené sú dve možnosti, ako môže byť celá križovatka pospájaná bez toho, aby sa čiary pretínali. Samozrejme existujú aj ďalšie možnosti. V prvej fáze kreslenia je jedno, akú možnosť si vyberieme, zvolíme si ľubovoľnú.

Takto dostaneme niekoľko nepretínajúcich sa čiar, ktoré dokopy tvoria celý obrázok. Pre tretí príklad z podúlohy b) by to mohlo vyzerať napríklad tak, ako na nasledujúcom obrázku:

V druhom kroku celého postupu sa budeme snažiť z veľa cyklických čiar spraviť jednu. Tieto cyklické čiary budeme volať cykly. Ak už náhodou je celý obrázok tvorený len jedným cyklom, sme hotoví a máme riešenie úlohy.

V opačnom prípade zoberieme ľubovoľné dva cykly, ktoré sa dotýkajú. (V našich obrázkoch kreslíme tak, že sa len takmer dotýkajú, pre lepšiu prehľadnosť). Cykly sa dotýkajú vtedy, keď majú nejakú spoločnú križovatku a zároveň neexistuje žiaden iný cyklus, ktorý by ich oddeľoval (t.j. vieme sa dostať od jedného cyklu k druhému bez toho aby sme museli prejsť cez nejaký iný cyklus). Keď z každej križovatky trčia 4 čiary, tak sa všetky cykly, ktoré majú spoločnú križovatku dotýkajú. Úloha je v takomto prípade trocha jednoduchšia (potom nám stačí riešiť predošlú, jednoduchšiu úlohu).

Dobre, tak teda zoberieme nejaké dva cykly, ktoré sa dotýkajú (vždy také musia existovať, zamyslite sa prečo) a v ich spoločnej križovatke ich prepojíme. Na obrázku je znázornené, ako by sme mohli prepojiť dve červené čiary, ktoré majú spoločnú zelenú križovatku.

Križovatky, z ktorých trčia 4 čiary sa prepájajú veľmi jednoducho, keďže tam sú len dva spôsoby ako môže križovatka vyzerať, jednoducho zmeníme jeden spôsob za druhý. Pre väčšie križovatky sa dá tiež ľahko vymyslieť spôsob ako ich prepojiť.

Vieme teda zobrať dotýkajúce sa cykly a spojiť ich do jedného (bez toho aby sa ostatné cykly zmenili), čím zmenšíme počet cyklov o jedna. Po niekoľkých takýchto úpravách nám teda zostane len jediný cyklus, ktorý je riešením našej úlohy.

To čo sme si práve predviedli je postupnosť krokov (algoritmus), ktorý nájde pre ľubovoľný obrázok nakresliteľný jednou čiarou taký nákres, ktorý sa nikde nepretína.

Pozrime sa ešte na to, čo sa nám podarilo dokázať. V časti b) sme ukázali, že obrázok sa dá nakresliť jednou nepretínajúcou sa čiarou, iba ak z každej križovatky vychádza párny počet čiar. V časti c) sme si potom ukázali postup, ako sa dá ľubovoľný takýto obrázok nakresliť. Uvedomme si, že tieto dva výsledky nám popisujú všetky obrázky, ktoré sa dajú nakresliť jednou čiarou – stačí ak z každej križovatky vedie párny počet čiar. Je to teda nutná a zároveň postačujúca podmienka.

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ť.