Zoznam úloh

5. Konzultácia Machinelearningu Slava (κ ≤ 7)

Zadanie

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]


  1. Hráč má víťaznú stratégiu, ak si vie svojimi ťahmi zaručiť výhru bez ohľadu na to, ako hrá jeho súper.

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č.

Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný matematický seminár zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty