6. Kompulzorná Mestská Súťaž vzorové riešenie

Pri hľadaní víťazných stratégií často tvoríme stratégie tak, že reagujú na ťah súpera. Keď chceme nájsť najmenšie \(n\), pre ktoré sedlák 2 vie vyhrať, musíme dokázať, že pre všetky menšie \(n\) vie vyhrať sedlák 1. Pozrime sa teda najprv na jeho stratégiu.

Hlavnou myšlienkou stratégie pre sedláka 1 bude, že si mestá budeme chcieť rozdeliť do dvojíc, pričom dve mestá v dvojici nikdy nebudú spojené cestou. Sedlák 1 sa bude usilovať o to, aby na konci hry ostala práve jedna z takýchto nespojených dvojíc, čím vyhrá. Na začiatku sedlák 1 zmaže niektoré mesto, čím ostane párny počet miest. Potom vždy zmaže druhé mesto v dvojici, z ktorej v predchádzajúcom ťahu zmazal mesto sedlák 2. Sedlák 1 je ten, kto tvorí mapu, a teda môže nakresliť všetky cesty okrem ciest medzi svojimi vybranými \(1009\) dvojicami miest.

Všetkých dvojíc miest je \(\binom{2019}{2} = \frac{2019 \cdot 2018}{2}\), pričom \(\binom{2019}{2}\) je kombinačné číslo, ktoré nám vyjadruje, koľko existuje dvojíc z \(2019\) prvkov. Sedlákovi 1 stačí vynechať \(1009\) z nich. Ak teda \(n \leq \binom{2019}{2}-1009\), sedlák 1 má víťaznú stratégiu, ktorá funguje presne takto:

1. Sedlák 1 si na začiatku popáruje mestá do \(1009\) dvojíc, jedno ostane nespárované.

2. Medzi všetky dvojice miest okrem týchto \(1009\) párov pridá cestu, čím vznikne \(\binom{2019}{2}-1009\) ciest. Ak je \(n\) menšie, tak nejaké cesty nepridá, na stratégiu to nemá vplyv.

3. V prvom ťahu sedlák 1 zmaže nespárované mesto.

4. V každom ďalšom ťahu zmaže sedlák 1 mesto, ktoré je vo dvojici s mestom, ktoré práve zmazal sedlák 2. V každej dvojici po sebe idúcich ťahov (najskôr sedlák 2 a potom sedlák 1) zmizne jedna dvojica miest.

5. Keď už budú existovať iba \(2\) mestá, je to jedna z dvojíc, ktorú si sedlák 1 zvolil na začiatku, teda nie sú spojené cestou, čiže sedlák 1 vyhral.

Pozrime sa teraz na prípad, kedy \(n \geq \binom{2019}{2}-1008\). To už máme cesty takmer medzi každou dvojicou miest. Presnejšie, existuje najviac \(1008\) dvojíc miest, ktoré nie sú spojené. Všimnime si, že sedlák 1 má \(1009\) ťahov a sedlák 2 má \(1008\) ťahov (aby nakoniec ostali práve dve mestá). Sedlák 2 vie teda (nezávisle na ťahoch sedláka 1) v každom svojom ťahu zmazať jedno mesto z niektorej nespojenej dvojice. Ak už z každej nespojenej dvojice zmazal aspoň jedno mesto, ďalšie ťahy môže robiť ľubovoľne (napríklad ak \(n\) je ešte väčšie alebo nejaké mesto patrilo do viacerých dvojíc atď.). V každom prípade z každej dvojice pôvodne nespojených miest bolo aspoň jedno mesto zmazané, a teda dvojica miest, ktorá ostala na konci, je nutne spojená cestou a sedlák 2 vyhral.

Ukázali sme, že najmenšie \(n\), pre ktoré ma sedlák 2 víťaznú stratégiu, je \(\binom{2019}{2}-1008=2018 \cdot 1009 +1\).

Poznámky opravovateľa

Mnohí z vás si poriadne neuvedomili, čo všetko zadanie úlohy požadovalo. Keďže máme hľadať najmenšie celé \(n\) spĺňajúce danú podmienku, musíme ukázať, že pre všetky menšie \(n\) má víťaznú stratégiu sedlák 1, zatiaľ čo pre nájdené \(n\) má víťaznú stratégiu sedlák 2. Keď ukazujeme, že niektorý sedlák má víťaznú stratégiu, musí táto stratégia fungovať bez ohľadu na to, čo robí druhý sedlák.

Mnohé riešenia postupovali nesprávne tak, že našli nejaké rozmiestnenie ciest (väčšinou sa zvolilo \(1010\) miest, ktoré sa pospájali všetky navzájom a ešte sa napojili na všetky zvyšné mestá, čím vzniklo \(\binom{1010}{2}+1010 \cdot 1009\) ciest, asi o štvrtinu menej ako \(n=\binom{2019}{2}-1008\)) a o tomto rozmiestnení ukázali, že ak doň pridáme ľubovoľnú ďalšiu cestu, sedlák 2 vyhrá. To však nie je správne, pretože sedlák 1 môže cesty nakresliť úplne inak (ako môžete vidieť v riešení) a vyhrať aj pri ešte vyššom počte ciest.