Slavo sa rozhodol naučiť počítač hrať nasledovnú hru:
Najprv Slavo nakreslí do roviny $n$ bodov. Potom počítač ofarbí tieto body dvomi farbami, zelenou a červenou. Nakoniec Slavo nakreslí do roviny kruh. Pokiaľ sa všetky zelené body nachádzajú vnútri kruhu (alebo aj na obvode) a všetky červené body mimo kruhu, tak Slavo vyhrá. Inak vyhrá počítač.
Po chvíli učenia bol Slavo s výsledkom spokojný, preto sa rozhodol otestovať počítač proti skúsenému oponentovi – Maťkovi. Maťko to však vyhlásil za príliš informatickú úlohu a odmietol to rátať. Dokážete úlohu vyriešiť a pomôcť Slavovi? V závislosti od prirodzeného čísla $n$, určte, kto má vyhrávajúcu stratégiu.[^1]
Keďže zadaná úloha sa značne mení podľa toho, aké $n$ si Slavo zvolí, skúsme sa najprv pozrieť na nejaké prípady pre malé $n$. Začnime pre $n=1$. V tomto prípade pre ľubovoľné ofarbenie počítačom vieme povedať, že určite vyhrá Slavo (premyslenie necháme na čitateľa). Pri $n=2$ je pre ľubovolne ofarbenie ľahko dokázateľné, že Slavo určite vyhrá (tento dôkaz tiež necháme na predstavivosť čitateľa).
Pri prípade $n=3$ to už začne byť zaujímavejšie. V prípade, ak by tieto body boli umiestnené na priamke, stačí počítaču len zafarbiť krajné body zelenou a stredný bod červenou farbou. V takomto prípade už Slavo určite nevie nakresliť kruh. V tomto prípade by vyhral počítač. Slavo je ale mladý šibal a môže si vybrať, ako nakreslí tieto body do roviny. Stačí mu nakresliť tieto body tak, aby tvorili vrcholy trojuholníka. V tomto prípade sa stáva znovu víťazom Slavo.
Zatiaľ nám vychádza, že Slavo vždy vyhrá. začína to preňho vyzerať sľubne. Pokračujme ale ďalej a pozrime sa aj na prípad pre $n=4$. Ak chce mať Slavo šancu vyhrať, môže usporiadať body do roviny dvomi spôsobmi (ako už vieme, nechce aby nejaké $3$ ležali na priamke).
Jedným spôsobom by bolo usporiadať body do nekonvexného štvoruholníka. To si vieme ľahko predstaviť ako tri body vo vrcholoch trojuholníka a štvrtý niekde vo vnútri trojuholníka. Hneď vidíme, že ak sa počítač rozhodne zafarbiť bod vo vnútri trojuholníka červenou farbou a vrcholy trojuholníka zelenou farbou, Slavo prehrá.
Druhým spôsobom by bolo usporiadať ich do konvexného štvoruholníka. Očividne problémový bude práve prípad, kedy sú vyfarbené body na jednej uhlopriečke zelenou farbou a body na druhej uhlopriečke červenou farbou (zvyšné teda radi prenecháme čitateľovi). Nakreslime si dva body do roviny a označme ich $A$ a $C$ a bez ujmy na všeobecnosti vyfarbíme tieto body zelenou farbou. Nakreslime si kružnicu $k$ tak, že tieto body $A$ a $C$ ležia v kruhu ktorého hranicou je kružnica $k$. Ak Slavo chce vyhrať, musel by červené body $B$ a $D$ umiestniť mimo kruhu ohraničeného kružnicou $k$. Aby body $B$, $D$ tvorili uhlopriečku konvexného štvoruholníka $ABCD$, tak sa musia nachádzať v opačných polrovinách určenými priamkou $LR$. Spravme si ešte priamku prechádzajúcu bodmi $A$ a $C$ a jej prieniky s kružnicou $k$ označme $L$ a $R$.
Poďme sa pozrieť, čo vieme povedať o uhloch v takomto útvare. To, že bod $B$ leží vo vonkajšej oblasti kružnice $k$, vieme pekne uchopiť pomocou obvodových uhlov. V takejto situáii musí platiť $$|\sphericalangle LSR| > |\sphericalangle LBR| \geq |\sphericalangle ABC|,$$ pričom $\sphericalangle LSR$ je obvodovým uhlom nad tetivou $LR$ v polrovine $LRB$. Analogicky pre druhý bod dostávame: $$|\sphericalangle LHR| > |\sphericalangle LDR| \geq |\sphericalangle ADC|.$$ Opäť platí, že $\sphericalangle LHR$ je obvodovým uhlom nad bodmi $L$ a $R$. Vieme, že pre obvodové uhly zodpovedajúce rovnakej tetive, ale v opačných polrovinách, platí: $$|\sphericalangle LHR| + |\sphericalangle LSR| = 180^\circ.$$ Platí teda: $$180^\circ > |\sphericalangle ABC| + |\sphericalangle ADC|.$$ Počítač si ale môže zvoliť, ktoré body zafarbí akou farbou. Stačí mu zafarbiť červenou farbou tie body na uhlopriečke, ktorých súčet prislúchajúcich vnútorných uhlov je aspoň $180^\circ$. Zvyšné dva body zafarbí zelenou farbou. Vtedy by pre súčet uhlov prislúchajúcich červeným bodom platil nasledovný vzťah: $$180^\circ > |\sphericalangle ABC| + |\sphericalangle ADC| \geq 180^\circ.$$ Dostávame jasný spor, teda Slavo by nevedel nakresliť pre tento prípad kruh tak, aby vyhral. Pre prípad $n=4$ má teda už víťaznú stratégiu počítač.
Čo sa deje pre $n>4$? Zoberme z týchto bodov ľubovoľné štyri. Počítač ich ofarbí tak, ako sme si ukázali pre $n=4$. Na ofarbení a usporiadaní ostatných bodov potom už nezáleží, nakoľko či budú v kruhu alebo mimo kruhu zelené alebo červené body, už Slavovi nepomôže splniť podmienku na výhru.
Vyšlo nám teda, že pre $n\leq3$ má víťaznú stratégiu Slavo a pre $n\geq4$ má už víťaznú stratégiu počítač.
Korešpondenčný matematický seminár zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Intenzívny matematický zážitok v lete
Tímová matematická súťaž pre stredoškolákov
Knižnica všemožných matematických múdrostí