6. Kolonizácia Morského Súostrovia vzorové riešenie

Dobrý spôsob, ako skúmať takéto hry, je pozrieť sa na to, ako by malo vyzerať súostrovie, keď už niektorý námorník nemá inú možnosť ako prehrať. Takúto situáciu budeme nazývať prehrávajúca pozícia. Ďalej si nazveme nekolonizovaný ostrov taký, na ktorý nevedie cesta zo žiadneho obývaného ostrova, a zvyšné ostrovy kolonizované. Iste každý ostrov v prehrávajúcej pozícii je kolonizovaný, lebo ak by nebol kolonizovaný, tak hráč môže stavať most naň. Zároveň však už nevie postaviť žiaden most medzi žiadnymi ostrovmi jednej či druhej časti súostrovia, lebo inak by taký most postavil a neprehral by. Čo znamená, že v prehrávajúcej pozícii máme dve časti súostrovia, medzi ktorými nie sú mosty a vo vnútri častí sú samé mosty.

Všimnime si, že pred každým ťahom Modrobrady je postavený párny počet mostov a pred ťahom Zelenovlasa nepárny počet. Ak je v prehrávajúcej pozícii Modrobrada, musí byť postavený práve párny počet mostov. Ak Zelenovlas, tak nepárny. Pozrime sa, koľko mostov sa dá postaviť v časti súostrovia s \(k\) ostrovmi. To vieme zistiť následujúcou úvahou. Vyberieme ostrov a z neho postavíme všetky mosty, tých je \(k-1\). Potom sa pozrieme na ďalší a vieme postaviť už len \(k-2\) mostov. Takto pokračujeme a dostaneme súčet \(1+2+3+4+ \dots + k-1=\frac{(k-1)k}{2}\).

Zoberme si prehrávajúcu pozíciu, v ktorej je v jednotlivých častiach súostrovia \(k\) a \(n-k\) ostrovov. Počet mostov, ktoré sa dajú postaviť vnútri týchto častí je teda \(\frac{(k-1)k}{2}+\frac{(n-k-1)(n-k)}{2}\). Nás zaujíma parita tohto výrazu, lebo ako sme ukázali, parita môže hrať dôležitú úlohu pri prehrávajúcich pozíciach. Výraz upravíme na \(\frac{(n-1)n}{2}+k(k-n)\) a môžme sa pozerať na jednotlivé členy a ich parity v závislosti od \(n\) a \(k\). Vidíme, že \(\frac{(n-1)n}{2}\) je síce celé, lebo súčin dvoch po sebe idúcich čísel nutne obsahuje párne číslo, ale nemáme zaručenú párnosť celého výrazu. Taktiež nevieme moc povedať o parite výrazu \(k(k-n)\), totiž nie je jednoznačná. Avšak v závislosti od \(n\) by sme mohli vedieť niečo povedať. Tak ako v prípade celočíselnosti zlomku \(\frac{(n-1)n}{2}\), kde sme využili po sebe idúce čísla, tak keď zoberieme rozdiel dvoch čísel nepárny, tak dostaneme súčin párny. Teda ak \(n\) bude nepárne, tak súčin \(k(k-n)\) bude párny, a keď \(n\) bude párne, tak nevieme zatiaľ nič viac povedať, lebo \(k\) môže byť stále párne alebo nepárne. Preto rozlíšime párne \(n\) a nepárne.

Pre nepárne \(n\) je výraz \(k(k-n)\) párny, a teda jeho parita závisí už len na tom, či \(n(n-1)\) je deliteľné štyrmi. Keď sa \(n\) dá zapísať ako \(n=4l+1\), tak dostávame párny výraz \(\frac{(n-1)n}{2}\). V takom prípade je v každej prehrávajúcej pozícii postavený párny počet mostov. Preto sa Zelenovlasovi nikdy nestane, že by bol v prehrávajúcej pozícii. Teda zakaždým vie postaviť most tak, aby neprehral, čo mu prinesie výhru. Podobne pre \(n=4l+3\) dostaneme nepárny počet mostov v každej prehrávajúcej pozícii a podobným spôsobom vie vyhrať Modrobrada.

Pre párne \(n\) majú počty mostov v prehrávajúcich pozíciách rôzne parity. Preto nebude námorníkom stačiť hrať len tak, ale budeme musieť pre niektorého z nich nájsť sofistikovanejšiu stratégiu. My ukážeme, že víťaznú stratégiu má v tomto prípade Zelenovlas. Keďže je \(n\) párne, vieme ostrovy rozdeliť do párov, pričom ostrovy obývané kmeňmi \(A\), \(B\) budú spolu v páre. Zelenovlasova stratégia bude spočívať v tom, že bude s využitím párov „kopírovať“ ťahy Modrovlasa. Ak teda Modrobrada postaví most medzi ostrovmi \(O\) a \(S\), tak Zelenovlas si zoberie pár ostrova \(O\) a pár ostrova \(S\) a postaví most medzi nimi. Bude to však vždy možné?

Uvedomme si, že takéto hranie Zelenovlasa zanecháva pred každým Modrovlasovým ťahom pekne symetrickú situáciu. To znamená, že ak je niektorý ostrov nekolonizovaný, tak rovnako jeho pár je nekolonizovný (a naopak). Ak je niektorý ostrov kolonizovaný jedným kmeňom, tak jeho pár je kolonizovaný druhým kmeňom. Podobne to platí aj pre mosty: dva ostrovy sú spojené mostom práve vtedy, keď sú ich páry spojené mostom. Z týchto úvah dostávame, že ak Modrobrada môže postaviť most medzi ostrovmi \(O\) a \(S\), tak aj Zelenovlas môže postaviť most medzi ich pármi. Takouto stratégiou si Zelenovlas zabezpečí, že po každom ťahu Modrovlasa bude môcť postaviť most a neprehrať. To bude opakovať, až raz Modrobrada bude nútený prepojiť dva kmene a prehrá. Takýto prístup využívajúci symetrickosť situácie je v problémoch s hrami celkom častý.

Takže Modrobrada vyhrá iba keď \(n=4l+3\), inak vyhrá Zelenovlas.