Do ukončenia našej súťaže chýba ešte 5 úloh. Neváhajte poslať aj niečo jednoduchšie (najmä vlastných nápadov tu zatiaľ veľa nemáme); napríklad také, ako je úloha, ktorá ma napadla dnes: Máme pravouhlú mriežku zostavenú z n × m úsečiek, kde n aj m sú nepárne čísla. Ukážte, že nie je možné po nej prejsť všetkými uzlovými bodmi tak, aby sme každý z nich navštívili práve raz a nakoniec sa vrátili do toho uzlového bodu, v ktorom sme začali. T.j. chceme dokázať, že v príslušnom grafe neexistuje hamiltonovská kružnica.
Jeden neúspešný pokus o uzavretú hamiltonovskú prechádzku na mriežke 5 × 5 je znázornený na ilustračnom obrázku vľavo hore.
Poznámka 6.1.: V komentári nám misof formuloval zaujímavú úlohu s trochu podobným námetom (aj keď ťažšiu); neprehliadnite!
Komu sa úloha zdá (ako mne :) ) priľahká, tak tu je ťažšia.
OdpovedaťOdstrániťMáme takú istú mriežku ako v zadaní, s oboma rozmermi nepárnymi. Len tentoraz nebudeme cestu kresliť sami.
Presnejšie, dvaja hráči hrajú na našej mriežke takúto hru: Prvý položí na niektorý mrežový bod figúrku, druhý potiahne na niektorý susedný bod, prvý potiahne na niektorý susedný bod, atď dokola. Figúrka za sebou kreslí čiaru, a tá musí tvoriť cestu -- teda nesmie ísť žiadnym bodom dvakrát. Prehráva ten, kto už nemôže potiahnuť.
Nájdite pre jedného z hráčov vyhrávajúcu stratégiu.
Miso: No, ak chcem obcas formulovat aj taku ulohu, ktoru ma sancu samostatne vyriesit aj povedzme prvak na gymnaziu, tak musi byt pre Teba nutne prilahka. :-)
OdpovedaťOdstrániťTa hra je naozaj zaujimava; dakujeme.
Mne sa úloha nezdá priľahká, aj keď gymnázium je už za mnou :-), tak som ju dnes skúsil pri obede vyriešiť:
OdpovedaťOdstrániťPodmienka, že sa vrátime do vrcholu, z ktorého sme vyšli sa dá vyjadriť tak, že ak kedykoľvek počas cesty urobíme krok "na sever", budeme časom musieť urobiť krok "na juh", podobne na ďalšie "svetové strany".
To, že prejdeme všetky vrcholy, každý práve raz, sa zas dá vyjadriť tak, že cesta sa bude skladať presne z toľkých úsečiek, koľko vrcholov má mriežka.
Tieto dve podmienky už spolu dávajú odpoveď. V mriežkach n x m kde n aj m sú nepárne čísla je počet uzlových vrcholov nepárny, teda uzavretá cesta prechádzajúca cez všetky vrcholy práve raz, by musela mať súčasne nepárny počet úsečiek (podmienka o vrcholoch) aj párny počet úsečiek (aby bola uzavretá).
Ahoj Rasťo. Pekné riešenie. Ja sám som si poprivymyslel podobné riešenie:
OdpovedaťOdstrániťOčíslujeme si uzlové body "do šachovnice", povedzme číslami 0 a 1. Je zrejmé, že každá hrana má na jednom konci uzol očíslovaný 0 a na opačnom uzol očíslovaný 1 (t.j. náš graf je bipartitný).
Takže nech by sme už išli akokoľvek, tak po nepárnom počte krokov (toľko je v našom grafe uzlov a toľko by musela mať dĺžku požadovaná kružnica) budeme nutne v uzle očíslovanom inak ako je očíslovaný náš počiatočný uzol. T.j. po nepárnom počte krokov sa nemôžeme vrátiť do pôvodného uzla.
Vlastne môžeme vysloviť všeobecnejšie tvrdenie a to že žiadny bipartitný graf s nepárnym počtom vrcholov nemôže obsahovať Hamiltonovskú kružnicu.