Řešení pro Úkol 5-2 – Velká mela

O přestávce se strhla velká mela, paní učitelka Pavouková se jen tak tak stačila schovat za katedru, když zaslechla výkřik „Hej, dáme na pětadvacet!“ a žáci se pustili jeden do druhého. Dál už to bylo velice nepřehledné, nevíme, kdo se pral s kým, zůstaly jen tyto poznámky v žákovských knížkách:

• Dan zapálil oheň.
• Olga vytáhla pistoli.
• Alča přivedla vlka.
• Honzík vylezl na strom.
• Ája cákla vodou.
• Evička nasadila masku ďábla.
• Sabina měla opičku.
• Simona hodila kámen.
• Radek píchal nůžkami.
• Éda odhodil dynamit.
• Erwin vyfouknul vzduch.
• Matěj seslal blesk.
• Ýgar byl jak mimozemšťan.
• Barča vrazila do kolemjdoucího muže.
• Richard hodil houbou.
• Samík vypustil hada.

Ája sice byla nadšená, že duel vyhrála, ale jako dívenka se trochu styděla za poznámku v žákajdě, tak za sebe příští přestávku poslala do dalšího kola kamarádku Nelu. Danovi se zdálo nefér, že by měl soupeřit s někým odpočinutým, zvlášť teď po tělocviku, kdy je celou hodinu učitel zkoušel a řadil lepší směrem k levé straně telocvičny, což znamenalo hodně popocházení, tak za sebe poslal Olivera. Evička a Éda nominovali Čendu a Kubu, Erwina vystřídal Jiřík, Matěj předal štafetu Yloně a Ýgar s Richardem za sebe poslali Rebeku a Terku. Leč to vedlo k dalším poznámkám v žákovských knížkách:

• Nela pustila do školy cizí ženu.
• Terka přinesla švába.
• Kuba se schoval za papír.
• Jiřík stříknul vodu.
• Oliver vypustil draka.
• Ylona má v aktovce atomovku.
• Rebeka hodila kámen.
• Čenda vytasil nůžky.

Nela za sebe poslala Oskara, Jiříka a Rebeku nahradili Matouš s Eliškou a Čendu střídala Lucka. Bohužel učitelé pro jejich snažení opět neměli pochopení:

• Matouš napřáhl nůžky.
• Lucka rozlila vodu.
• Oskar ohrožoval kamenem.
• Eliška zapálila oheň.

Lucka a Eliška byly tak překvapené, že porazily kluky, že o tom štěbetaly ještě o další hodině. Ta byla hrozně nudná, protože učitel na pěstitelky se je snažil naučit lézt po stromě. Nebylo to moc platné, pojmy jako preorder traversal totiž žákům opravdu nic neříkaly.

O příští přestávce vystřídal Lucku Ota a místo Elišky se do souboje vrhnul Toník:

• Toník hrozil kamenem.
• Ota ztupil nůžky.

Toník tedy celý souboj vyhrál, ale protože musel v ředitelně vysvětlovat svoje chování, tak čokoládu pro vítěze slupla:

• Karolína.

Řešení

Není divu, že dostali žáci tolik poznámek do žákovských, když nosí do školy atomovku nebo švába! Co je to za podivný zápas? Houbou snad, ale opravdu někdo hodil kamenem? Když budete chvíli příběh číst, asi zjistíte, že pod maskou vykukují (zejména ke konci dost výrazně) některé známé pojmy, třeba ztupil nůžky by vás mohlo navést. I ten papír se v šifře objevuje. Žáci se totiž neperou doopravdy, ale hrají turnaj ve hře Kámen, nůžky, papír, ovšem v nějaké podivné rozšířené variantě. Zmiňují se o variantě s 25 symboly.

Nezbývá, než ji vyhledat na internetu, kromě varianty Kámen, nůžky, papír, tapír, Spock, kterou proslavil Sheldon Cooper v seriálu Big Bang Theory, existují varianty na 7, 9, 11, 15, 25, ale i 101 symbolů!

Strom výsledků zápasů budeme kreslit odshora od Karolíny, která snědla čokoládu pro vítěze. V zadání je přímo napsáno, že zastoupila Toníka, který vyhrál nad Otou, aby ne, kámen tupí nůžky. Také z textu šifry víme, že vítěze máme řadit směrem k „levé straně tělocvičny“. Dokonce i částěčně víme, jak bude stromeček pokračovat dál, protože Eliška a Lucka vyhrály. Ale s kým hrály? Jde to nějak zjistit, aniž bychom hádali?

               K
         _____/ \_____
        /             \
       T               O
     /   \           /   \     
    /     \         /     \        
   E       ?       L       ?

Zkusíme zaznamenat možné výsledky do tabulky čistě podle pravidel ve hře kámen, nůžky, papír hrané na 25 symbolů. Protože holky vyhrály, škrtneme všechny možnosti, kde prohrávají a ekvivalentně i varianty, kde kluci vyhrávají. Jak vidíte, situace už je jednoznačná – oheň poráží nůžky (Matouše) a kámen prohrává s vodou (Oskarem).

Matouš	nůžky	poráží
		prohrává	voda, kámen, oheň
Lucka	voda	poráží	nůžky, kámen, oheň
		prohrává
Oskar	kámen	poráží	oheň, nůžky
		prohrává	voda
Eliška	oheň	poráží	nůžky
		prohrává	kámen, voda

Podle stejného algoritmu můžeme pokračovat i v další vrstvě zápasu, řešení se dá opět najít jednoznačně. Sestavíme tabulku, tentokrát pro jednoduchost nebudeme psát zápasy z obou stran, ale pro kontrolu vyplnění je úplná tabulka lepší. Všimněte si, že pouze voda jako jediná může porazit atomovku. Proto u vody i atomovky můžeme škrtnout všechny ostatní možnosti. Navíc můžeme vodu a atomovku škrtnout u všech ostatních zápasů.

Nela	žena	poráží	šváb, papír, voda, drak
Terka	šváb	prohrává	žena, nůžky, kámen
Kuba	papír	prohrává	nůžky, žena, šváb
Jiřík	voda	poráží	drak, atomovka, kámen, nůžky
Oliver	drak	prohrává	žena, šváb, papír, voda
Ylona	atomovka	prohrává	šváb, papír, voda, drak
Rebeka	kámen	poráží	nůžky, žena, šváb
Čenda	nůžky	poráží	žena, šváb, papír

Když tuto eliminaci provedete a zjistíte, že Jiřík porazil Ylonu, upřesní se vám kámen a drak a pak už je vše jasné. I v posledním kole zápasu, kde je celkem 16 soupeřů, se podaří podle stejných pravidel zjistit jednoznačné řešení a tím pádem můžete nakreslit pavouka zápasů, resp. binární strom:

               K
         _____/ \_____
        /             \
       T               O
     /   \           /   \     
    /     \         /     \        
   E       M       L       O
  / \     / \     / \     / \
 R   T   J   Y   Č   K   N   O
/ \ / \ / \ / \ / \ / \ / \ / \
Ý S R O E S M B E S É H Á R D A

Písmenka ve stromu jsou utvořena z prvních písmenek jmen zúčastněných žáků. Vítězové jsou vždy vlevo. Přečteme strom algoritmem preorder traversal, při kterém vždy začínáme nahoře a vždy přečteme pímenko na rozcestí a pak pokračujeme levou větví a po návratu z ní pravou. Čteme tedy „který strom je symbol českého národa“ a odpověď je lípa.