Úloha 5.u4: N-hlavá saň (4 b)

Zadáno v čísle 22.5.

Řešeno v čísle 22.7.

Zadání

Chytrý Honza se rozhodl zachránit zakletou matfyzačku, kterou unesla strašlivá $N$-hlavá saň a hlídá ji ve svém doupěti pod Malostranským náměstím. Honza nechce nic ponechat náhodě, a tak si připravuje taktiku, jak saň porazit. Taková $N$-hlavá saň se skládá ze dvou základních částí – krků a uzlů. Každý krk vždy spojuje dva uzly. Nejdůležitějším uzlem je tělo. Z toho vyrůstá několik krků, na konci každého je uzel, ze kterého může vyrůstat několik krků atd. (viz Obrázek 1.a). Každý uzel má úroveň, podle toho, jak daleko je od těla, tedy tělo je na úrovni nula, uzly spojené s krkem jsou na úrovni jedna, uzly, které jsou dva krky daleko od těla jsou na úrovni dva a tak dále.

a) Příklad $N$-hlavé saně
b) Před useknutím hlavy $u$
Obrázek 1: Saně

Honza chce saň zabít tím, že jí postupně usekne všechny hlavy (to jsou uzly, ze kterých nevede žádný krk do vyšší úrovně). Jakmile sani zbývá jen tělo, zemře. V každém kroku si Honza vybere jednu hlavu a usekne ji. Ale ouha, sani hlavy dorůstají. Předpokládejme, že v $K$-tém kroku usekne Honza hlavu $u$, označíme si $v$ uzel, ze kterého vede krk do $u$ a $S$ budeme říkat celé struktuře krků a uzlů, která vyrůstá z $v$ (včetně $v$, ale bez $u$). Ještě si označíme $w$ ten jediný uzel spojený krkem s $v$ takový, že $w$ je na nižší úrovni než $v$. Potom saň sice přijde o hlavu $u$, ale zároveň z $w$ vyroste $K$ nových kopií $S$. Usekne-li Honza hlavu, která vyrůstá přímo z těla, pak sani nic nedoroste. Příklad, jak může takové useknutí hlavy proběhnout, je na Obrázku 1.b a 2. Krom dorůstání může hlava vzniknout z libovolného uzlu, který přišel o všechny krky vedoucí do vyšší úrovně.

Obrázek 2: Po useknutí hlavy $u$ sani vyrostly nové hlavy

Ukažte, že Chytrý Honza dokáže zabít každou $N$-hlavou saň.

Řešení

Počet krků, které vyrůstají z uzlu $v$ a zároveň vedou do vyšší úrovně saně, si označíme $d_ v$, tomuto číslu budeme říkat stupeň $v$. Jinak řečeno, z uzlu $v$ vede jeden krk do nižší úrovně (kromě případu, kdy je $v$ tělo) a $d_ v$ krků do vyšší úrovně; uzly na nejvyšší úrovni mají stupeň nula. Nyní si popíšeme jednu z možných taktik, která Honzovi zaručí vítězství.

V jednom kole se Honza podívá na všechny uzly na předposlední úrovni a vybere si ty, které mají nejvyšší stupeň. Každému z těchto uzlů pak usekne libovolnou hlavu, která je na něj připojena. Sani doroste několik (přesněji řečeno $K$$K$-tém kroku) kopií každého takového uzlu, všechny už ale budou mít stupeň menší o jedna. Po každém kole se tedy Honzovi podaří snížit maximální stupeň na předposlední úrovni o jedna – tento postup se zastaví ve chvíli, kdy všechny uzly na předposlední úrovni mají stupeň nula. To ale znamená, že jsme zničili poslední úroveň saně. Teď už stačí jen opakovat tento postup ničení nejvyšší úrovně, dokud sani nezbude pouhé tělo.

Povšimněte si, že v důkazu jsme nepotřebovali vědět, kolik hlav sani dorůstá, stačilo nám pouze, že je to v každém kroku nějaký konečný počet. Možná ještě podivuhodnější vlastností tohoto problému je, že vůbec nezávisí ani na Honzově taktice. Ať už bude hlavy sekat v jakémkoli pořadí, po konečném počtu kroků sani zbude jen tělo. Dokázat toto silnější tvrzení je ale v jistém smyslu těžké (což se dá dokonce dokázat, i tento důkaz je nicméně těžký :-) ), zájemcům doporučujeme vyhledat na internetu heslo Hydra Game.

Vašek