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
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č.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.