Zadanie
Dante nemal čas vypĺňať súdne dokumenty, lebo ho čakala nočná nasáľačka. Revolver mal pripravený na najhoršie a jeho kokosáky ho ťažili v kapsách. Ako kráčal ulicou, zniesol sa pred neho muž s mechanickými krídlami a vyhŕkol: „Dante! Štváč Ernest sa dozvedel, že sa ho dnes v noci chystáme čapnúť! Zobral melanž a zdrhol lietadlom!“ „Tak to teda nie,“ zavrčal Dante. „Kúp si lístky, Watson, lebo nasadáme... do biznis triedy.“
Štváč Ernest uteká pred \(62\) policajtmi, ktorí ho prenasledujú po leteckej sieti USA. V USA je \(2020\) letísk, pričom medzi niektorými dvojicami letísk sú obojsmerné letecké spojenia. Každé spojenie spája práve dve letiská a medzi každými dvoma letiskami sa dá prepraviť využitím najviac dvoch leteckých spojov.
Počas prvého dňa sa \(62\) policajtov ľubovoľne rozmiestni po letiskách v USA, kľudne aj viacerí na to isté letisko. Potom cez prvú noc na niektoré letisko pricestuje Štváč Ernest, podľa svojej voľby. Po celý čas (teda už aj v prvú noc) majú Ernest aj prenasledovatelia informácie o polohách všetkých zúčastnených. Každý deň sa môže (ale aj nemusí) každý prenasledovateľ presunúť pomocou jedného leteckého spojenia z jeho letiska do nejakého iného letiska. Každú noc sa môže (ale nemusí) Štváč Ernest presunúť na iné letisko pomocou jedného leteckého spojenia. Ak sa nejaký policajt nachádza na letisku naraz so Štváčom Ernestom (je jedno či cez deň alebo v noci), Štváč Ernest je okamžite zatknutý. Dokážu policajti zatknúť Štváča Ernesta bez ohľadu na jeho stratégiu cestovania a bez ohľadu na to, ako vyzerajú letecké spojenia medzi letiskami v USA?
Ernest sa nechce vo svojom ťahu skončiť na letisku, ktoré je susedné s policajtom. Ak áno, tak cez deň sa ten policajt presunie na letisko kde je Ernest a zatkne ho. Takže otázka je, či sa vie Ernest pohybovať tak, že vždy bude aspoň na dva lety od každého policajta.
Ďalšie pozorovanie je, že keď je Ernest na letisku \(E\) s najviac (vrátane) \(62\) susednými letiskami, tak sa policajti vedia cez deň presunúť tak, že každý je v jednom z týchto susedov alebo jeho okolí – pretože z ľubovoľného letiska sa vedia dostať do suseda \(E\) najviac s dvoma letmi. To znamená, že buď by sa Ernest dostal vo svojom ťahu do letiska, v ktorom je policajt alebo do letiska, vedľa ktorého je policajt. Takže Ernest môže len sedieť a čakať kým ho druhý deň nezatknú alebo ho neobkolesia.
Ak máme letisko s aspoň \(63\) vrcholmi, tak do neho postavíme policajta a nech sa nehýbe. Teda pohnúť sa môže, ak by mal na susednom letisku Ernesta. Takto efektívne pokryjeme \(64\) letísk. Prestaneme ich uvažovať ako možnosti kam Ernest môže cestovať, zostane nám teda \(2020-64=1956\) letísk kam Ernest môže cestovať a \(61\) policajtov na pokrytie. Teraz ak Ernest je na letisku s najviac \(61\) susedmi (v novej letiskovej sieti), tak ho policajti vedia podobne dolapiť na najviac dva ťahy, takže sa musí nachádzať na letisku, ktoré má aspoň \(62\) susedov. Ale tak na to letisko posadíme policajta, a preto Ernestovi odoberieme ďalších \(63\) možností kam cestovať. Takto budeme pokračovať.
Postupne ak sme už rozostavili \(k\) policajtov do letísk s aspoň \(63-i\) linkami (\(i\) od \(0\) po \(k-1\)), tak ak je Ernest na letisku s najviac \(63-k-1\) susedmi, tak ho vieme na tri ťahy chytiť (podobný argument ako hore) alebo je to letisko s aspoň \(63-k\) linkami a tam umiestnime policajta.
Dostaneme súčet \(64+63+62+\dots+3 = 2077\) letísk, na ktoré Ernest nemôže cestovať. Čo je viac ako \(2020\), a preto vieme Ernesta zatknúť.
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ť.