Adventný Logboj - Adventný Logboj je individuálna súťaž v riešení logických úloh, v ktorej môžu súťažiť základoškoláci, stredoškoláci aj starší. Na stránke súťaže bude každý decembrový deň až do vianoc sprístupnená jedna úloha, … Prejsť na článok
×3. príklad - Vzorové riešenie
Zadanie
Máme mriežku 5 \times 5 štvorcov. Na hrany dĺžky 1 tejto mriežky umiestňujeme kobry dlhé 10 (lomená čiara). Vieme umiestniť 6 kobier tak, aby na každej hrane bol práve jeden kus hada?
Poznámka: Lomenou čiarou myslíme takú postupnosť úsečiek, ktoré na seba nadväzujú (majú spoločné koncové body). Čiara sa navyše nikdy sama so sebou nekrižuje, ani sa sama seba nedotýka.Vzorové riešenie
Skúsme si najprv spočítať, koľko má takáto mriežka hrán. V každom riadku a stĺpci máme po 5 hrán a riadkov aj stĺpcov tam je 6. Dokopy je to teda 6\cdot2\cdot5=60. Máme 6 hadov dĺžky 10, teda 60 kusov hada. Počty teda sedia, z tohto pohľadu by pokrytie všetkých hrán mohlo byť možné.
Ak sa však pokúsime kobry rozmiestňovať, nepodarí sa nám zadanie splniť. Možno si aj všimneme, že niektoré hrany sa nám pokrývajú nejako ťažšie (tie pri krajoch) a možno to súvisí aj s mrežovými bodmi (vrcholmi). Práve na tie sa skúsime zamerať.
Všimnime si, že keď cez vrchol mriežky prechádza had, musí vojsť cez jednu hranu a vyjsť cez druhú. Pri svojom prechode teda zaberie dve hrany. Bežným vrcholom, z ktorého vychádzajú 4 hrany teda prejdú dva hady. Na okraji mriežky ale máme vrcholy, z ktorých vychádzajú tri hrany. V týchto vrcholoch musí nejaký had začínať alebo končiť. Prechádzajúci had totiž zaberie dve z troch hrán, poslednú vyplní had už len tak, že príde a nemá kam ďalej ísť, alebo tam naopak začne.
Vrcholy, z ktorých vychádzajú tri hrany, sú na každej strane mriežky štyri, takže dokopy máme 4\cdot4=16 takýchto vrcholov. V každom z nich musí začínať alebo končiť had, inak nejaká hrana pri ňom isto ostane nezaplnená. K dispozícii máme šesť hadov a každý má dva konce, teda 12 koncov hada. Vidíme, že mriežka sa nedá vyplniť, lebo nemáme dosť koncov hada.