Úloha 2.u2: Cesta po sirkách (3 b)

Zadáno v čísle 23.2.

Řešeno v čísle 23.4.

Zadání

Mějme čtvercovou síť o velikosti 4$\times $4. Vezmeme si 16 sirek a uděláme na nich čárky následovně: na jednu sirku nakreslíme jednu čárku, na osm sirek dvě čárky, na sedm sirek tři čárky.

Položíme-li na políčko sirku s jednou čárkou, ukazuje ve směru hlavičky na sousední pole, sirka se dvěma čárkami o jedno pole dále a sirka se třemi čárkami na třetí políčko v daném směru. Podíváme se na pole, na které ukazuje sirka, a pokud na něm leží nějaká další, pokračujeme podle ní. Putování může skončit různě, nás však bude zajímat takové rozložení sirek, že se po navštívení šestnácté sirky vrátíme opět na začátek (viz Obr. 1).

Obrázek 1: Ukázka cyklu na síti s použitím sedmi sirek (jedna s jednou čárkou, tři se dvěma čárkami a tři se třemi čárkami).

Dokážete umístit všech 16 sirek na síť tak, aby tvořily uzavřenou cestu (viz Obr. 1)? Existuje jiné označení sirek, které umožní vytvořit delší uzavřenou cestu (za délku cesty se považuje počet políček)?

Řešení

Při řešení se nejdříve zamyslíme nad tím, jak můžeme umístit sirky se třemi čárkami. Proč začít zrovna jimi? Tento druh sirek je možné umístit pouze na okrajová pole čtvercové sítě. Kdybychom totiž uložili sirku se třemi čárkami na některé z vnitřních polí, ukazovala by mimo síť. Navíc pouze v rozích můžeme tříčárkované sirky položit dvěma způsoby, na ostatních okrajových polích musí sirka směřovat dovnitř, jinak by opět ukazovala mimo síť.

Celkem tedy máme 12 polí, kam můžeme umístit tříčárkové sirky na 7 tříčárkových sirek. Nemůžeme však použít všech osm polí zároveň. Kdybychom položili dvě sirky naproti sobě, vytvoříme cyklus. Z osmi polí, která jsou na okraji sítě, ale nejsou v rozích, můžeme použít pro tříčárkové sirky pouze 4, které nejsou protilehlé. Jak to vypadá s rohovými poli? Sirky musíme pokládat jedním směrem, protože kdybychom položili jednu sirku opačným směrem, opět vznikne cyklus. Při obsazení všech rohů vznikne cyklus o čtyřech sirkách, takže do rohů můžeme položit nejvýše 3 tříčárkové sirky. Celkem tedy máme poměrně přesně stanoveno, kde se musí nacházet tříčárkové sirky.

Nyní určíme polohu zbývajících sirek. Začneme uložením dvoučárkové sirky do posledního zbývajícího rohu. Můžeme ji položit dvěma způsoby. Dále pokládáme sirky tak, abychom umístili zbylé 4 tříčárkové sirky na okraj. Výsledná dvě možná řešení viz Obrázek 2. Délka cyklu je stejná jako součet čárek na všech sirkách, tedy 38.

Obrázek 2: Dvě možnosti, jak naskládat všech 16 sirek tak, aby tvořily uzavřený cyklus.

Jak je to s možností přeznačit sirky tak, aby vznikla delší uzavřená cesta? Problém si přeformulujeme: Hledáme přeznačení sirek tak, aby součet všech čárek byl větší než 38 a zároveň jsme z nich dokázali sestavit uzavřený cyklus.

Čtyř- a více čárkové sirky zřejmě použít nemůžeme, jelikož bychom se dostali mimo síť. Už při hledání uzavřeného cyklu ze všech sirek jsme si ukázali, že polí, kam je možné umístit tříčárkové sirky, je právě 7. Přeznačit dvou- nebo jednočárkovou sirku za tříčárkovou tedy nemůžeme. Zároveň máme jen jednu jednočárkovou sirku, takže nemáme možnost ponížit trojčárkovou sirku na dvojčárkovou a poté přeznačit ostatní sirky, aby se aktuální počet čárek zvýšil alespoň o dvě.

Zbývá tedy pouze možnost přeznačit jednočárkovou sirku na dvoučárkovou. Pro toto označení sirek však také nedokážeme nalézt uzavřený cyklus. Proč? Pokud chceme prodloužit původní cyklus, můžeme to udělat pouze tak, že si „zajdeme“ nějakým směrem. Když si ale „zajdeme“ dále jedním směrem, musíme se pak i vrátit. Délka cesty tak musí zůstat sudá, jak nahlédlo mnoho z vás. Zajímavý argument použil Mgr. Pavel Turinský. Obarvíme si čtvercovou síť jako šachovnici a všimneme si, že počet sirek, které ukazují na bílá pole, je stejný, jako počet sirek, která ukazují na černá pole. Tím, že přeznačíme jednočárkovou sirku na dvoučárkovou, změníme barvu pole, na které ukazuje. Jelikož žádnou jinou sirku nepřeznačujeme, způsobili jsme nerovnováhu mezi bílou a černou.

Z toho plyne, že nalezený cyklus je nejdelší možný. Existuje ještě jedno řešení o stejné délce, které se skládá z šesti tříčárkových sirek a devíti dvoučárkových sirek. Dokážeš ho najít?

Anet