Seminár 26: Kombinatorika II – hry s hľadaním víťaznej stratégie a logické úlohy.

Pretože prvočísel menších ako 100 je nepárny počet (25), ponúka sa hypotéza, že víťaznú stratégiu bude mať prvá hráčka. Ukážme, že to tak naozaj je. Táto hráčka si vopred v duchu spáruje (podľa spoločnej číslice) napísané prvočísla (dá sa to urobiť viacerými spôsobmi, uvedieme ten, pri ktorom v každom kroku párujeme najmenšie doposiaľ nespárované prvočíslo s najmenším ďalším doposiaľ nespárovaným prvočíslom so spoločnou číslicou): (2, 23), (3, 13), (5, 53), (7, 17), (11, 19), (29, 59), (31, 37), (41, 43), (47, 67), (61, 71), (73, 79), (83, 89); jediné zostávajúce nespárované prvočíslo 97 preto Gitka zmaže ako prvé a ďalej pri hre bude mazať vždy prvočíslo, ktoré je v páre s predchádzajúcim zmazaným prvočíslom. Týmto postupom musí vyhrať.

Komentár

Úloha je malým opakovaním toho, ktoré čísla do 100 sú prvočísla a môžeme ju využiť na pripomenutie definície prvočísla. Rovnako ako aj v nasledujúcich úlohách, aj tu môžeme študentov nechať najprv odohrať niekoľko hier a potom skúsiť ich čiastkové zistenia spoločne pretaviť do univerzálnej stratégie.

Úloha dvoch po sebe zotieraných čísel je v zadanej hre symetrická: ak je po čísle \(x\) možné zotrieť číslo \(y\), je (pri inom priebehu hry) po čísle \(y\) možné zotrieť číslo \(x\). Preto si môžeme celú hru (so zadaným číslom \(n\)) tak, že najskôr vypíšeme všetky takéto (nazývajme ich prípustné) dvojice \((x, y)\). Keďže na poradí čísel v prípustnej dvojici nezáleží, stačí vypisovať len tie dvojice \((x, y)\), v ktorých \(x < y\).

V prípade \(n = 6\) všetky prípustné dvojice sú \[(1, 3), (1, 4), (1, 5), (1, 6), (2, 5), (3, 5).\] Z tohto zoznamu ľahko odhalíme, že víťaznú stratégiu má (prvá) hráčka Marína. Ak totiž zotrie na začiatku hry číslo 4, musí Tamara zotrieť číslo 1, a keď potom Marína zotrie číslo 6, nemôže už Tamara žiadne ďalšie číslo zotrieť. Okrem tohto priebehu \(4 \rightarrow 1\rightarrow 6\) si môže Marína zaistiť víťazstvo aj inými, pre Tamaru ”vynútenými“ priebehmi, napríklad \(6\rightarrow 1 \rightarrow 4\) alebo \(4 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 2\).

V prípade \(n = 12\) je všetkých prípustných dvojíc výrazne väčšie množstvo. Preto si položíme otázku, či všetky čísla od 1 do 12 možno rozdeliť na šesť prípustných dvojíc. Ak totiž nájdeme takú šesticu, môžeme opísať víťaznú stratégiu druhej hráčky (Tamary): ak zotrie Marína pri ktoromkoľvek svojom ťahu číslo \(x\), Tamara potom vždy zotrie to číslo \(y\), ktoré s číslom \(x\) tvorí jednu zo šiestich nájdených dvojíc. Tak nakoniec Tamara zotrie aj posledné (dvanáste) číslo a vyhrá (prípadne hra skončí skôr tak, že Marína nebude môcť zotrieť žiadne číslo).

Hľadané rozdelenie všetkých 12 čísel do šiestich dvojíc naozaj existuje, napríklad \[(1, 4), (2, 9), (3, 8), (5, 12), (6, 11), (7, 10).\] Iné vyhovujúce rozdelenie dostaneme, keď v predošlom dvojice (1, 4) a (6, 11) zameníme dvojicami (1, 6) a (4, 11). Ďalšie, menej podobné vyhovujúce rozdelenie je napríklad \[(1, 6), (2, 5), (3, 10), (4, 9), (7, 12), (8, 11).\] Záver. Pre \(n = 6\) má víťaznú stratégiu Marína, pre \(n = 12\) Tamara.

Komentár

Úloha je náročnejšia ako predchádzajúca, no študenti by mali prvú časť zvládnuť samostatne, v časti druhej môžu svoje sily spojiť s ďalšími spolužiakmi, príp. stratégie, ktoré vymysleli, otestovať pri vzájomnej hre.

Víťaznú stratégiu má prvá hráčka: prvú mincu položí doprostred stola a v každom ďalšom kroku položí mincu na miesto súmerne združené podľa stredu stola s miestom práve položenej mince.

Komentár

Úloha je zaujímavým príkladom, kde zohráva špeciálnu úlohu jeden konkrétny bod hracej plochy. Nájdenie víťaznej stratégie je po uvedomení si tejto vlastnosti už úlohou jednoduchou. Na príklade tejto hry môžeme študentov upozorniť na ďalší všeobecný princíp, ktorý pri riešení matematických problémov môže prísť vhod – hľadanie symetrií, príp. špeciálnych bodov týchto symetrií a skúmanie ich vlastností, pričom symetrie nemusíme chápať nutne iba v geometrickom kontexte.

Slová ZÁPAL a \(STRUK\) nemajú spoločné písmená. Preto sa, ako vyplýva z odpovedí 1 + 2 a 0 + 2, medzi ich písmenami, ktoré dokopy tvoria množinu \(M= \{Z\), Á, \(P, A, L, S, T, R, U, K\}\), nachádza všetkých päť písmen hľadaného slova. V slove \(SKOBA\) majú byť práve tri z hľadaných písmen. Sú to teda písmená \(S, K, A\). (Zvyšné písmená \(B\) a \(O\) totiž do množiny \(M\) nepatria.) V slove \(CESTA\) majú byť len dve z hľadaných písmen, a obe na správnej pozícii. Sú to už nájdené \(S\) a \(A\), ktoré teda patria na tretie, resp. piate miesto hľadaného slova (a písmeno \(T\) môžeme z množiny \(M\) ”vylúčiť“). Písmeno \(K\) nemôže byť ani na prvom, ani na druhom mieste: vyplýva to z odpovedí pre slová KABÁT (0 + 3) a \(SKOBA\) (1 + 2). Takže je na štvrtom mieste a ostáva určiť prvé dve písmená. V slove \(STRUK\) sú len dve z hľadaných písmen (musia to teda byť \(S\) a \(K\)), obe na nesprávnych pozíciách. Preto z množiny \(M\) aj písmená \(R, U\) (a \(T\), ak sme to doteraz neurobili). Zvyšné dve hľadané písmená potom patria do množiny \(\{Z\), Á, \(P, L\}\). Z podmienok pre slovo KABÁT vyplýva, že jedno z nich je Á. V slove ZÁPAL je práve jedno písmeno na správnej pozícii. Keby to bolo \(Z\), nemali by sme kam uložiť písmeno Á. Takže Á je na druhom mieste a navyše môžeme vylúčiť písmeno \(Z\). Na prvom mieste hľadaného slova môže byť \(L\) alebo \(P\). Ľahko sa presvedčíme, že nájdené slová LÁSKA aj PÁSKA vyhovujú všetkým podmienkam úlohy.

Komentár

Úloha opäť nevyžaduje žiadne matematické znalosti, je však výbornou previerkou toho, ako sú študenti schopní narábať s veľkým množstvom informácií, nestratiť v nich prehľad a využiť ich na zdarné vyriešenie zadaného problému.

Poslední štyria hráči odohrali medzi sebou 6 partií, takže počet bodov, ktoré dokopy získali, je aspoň 6. Hráč, ktorý skončil na 2. mieste, teda získal aspoň 6 bodov. Keby získal viac ako 6, teda aspoň 6,5 bodov, musel by najlepší hráč (vďaka podmienke rôznych počtov) získať všetkých 7 možných bodov; porazil by tak i hráča na 2. mieste, ktorý by v dôsledku toho získal menej ako 6,5 bodov, a to je spor. Hráč v poradí druhý preto získal práve 6 bodov. Presne toľko ale získali dokopy i poslední štyria, a tak mohli tieto body získať len zo vzájomných partií, čo znamená, že prehrali všetky partie s hráčmi z prvej polovice výsledného poradia. Hráč, ktorý skončil na 6. mieste, preto prehral partiu s hráčom, ktorý skončil na 4. mieste.

Každý hráč odohral po jednej partii so zvyšnými štyrmi. Bolo teda odo hraných celkom \(\frac{1}{2}\cdot 5 \cdot 4 = 10\) partií, takže každý hráč získal práve 2 body. Sú len tri možnosti, ako získať odohraním štyroch partií 2 body, a podľa toho obsahovala celková tabuľka nanajvýš tri rovnocenné skupiny hráčov. Tieto skupiny, \(A, B\) a \(C\), uvádzame v poradí, v ktorom by sa v konečnej tabuľke umiestnili:

Skupina \(A\) obsahuje všetkých hráčov, ktorí majú po dvoch výhrach a dvoch prehrách. Skupina \(B\) pozostáva z hráčov s jednou výhrou, jednou prehrou a dvoma remízami. Skupina \(C\) obsahuje hráčov so štyrmi remízami.

Vojto a Tomáš sú jediní víťazi, preto nepatria do skupiny \(C\). Nepatria ani do skupiny \(B\), pretože v opačnom prípade by s nimi museli všetci traja hráči zo skupiny \(C\) s horším výsledkom remizovať (a každý hráč skupiny B má len dve remízy).

Z toho vyplýva, že Vojto a Tomáš majú po dvoch výhrach a dvoch prehrách a skupina \(C\) je prázdna. Zvyšní traja hráči tak majú po jednej výhre, jednej prehre a dvoch remízach, ktoré museli uhrať navzájom medzi sebou.
Záver. Peter a Martin spolu remizovali.

Iné riešenie*. Využijeme (nadbytočný) údaj, že Vojto porazil Petra: Keby mali Vojto a Tomáš po jednej výhre, jednej prehre a dvoch remízach, musel by aj Peter patriť medzi víťazov turnaja. Jediný v poradí nižší celkový výsledok sú totiž štyri remízy, Peter však jednu partiu prehral, a tak musel aj jednu vyhrať. Vojto a Tomáš majú 1preto po dvoch výhrach a dvoch prehrách. Ak Peter prehral s Vojtom, musel poraziť Tomáša. (Nemohol mať dve prehry, keďže bol v poradí nižšie ako Tomáš a Vojto. Ani nemohol s Tomášom, ktorý žiadnu remízu nemá, remizovať.) Potrebný druhý bod získal dvoma remízami – s Martinom a nepomenovaným piatym hráčom.
Záver. Peter a Martin spolu remizovali.

Riešenie rozdeľme podľa hodnoty čísla \(k\).

Ak \(k = 0\), je počet kociek pokrývajúcich dva krížiky rovný nule, preto vyhrá Simona.

Ak \(0 < k \leq 32\), umiestni Simona krížiky napr. iba na biele políčka šachovnice. Potom pod žiadnou kockou nie sú dva krížiky, preto vyhrá Simona.

Ak \(k > 32\), pričom \(k\) je párne, umiestni Simona 32 krížikov na biele políčka a zvyšné krížiky kamkoľvek. Potom pod párnym počtom kociek sú dva krížiky (takých kociek je totiž práve \(k - 32\), pretože každá dominová kocka pokrýva jedno biele a jedno čierne políčko šachovnice), takže vyhrá Simona.

Ak \(32 < k \leq 61\), pričom k je nepárne, nenapíše Simona krížiky do troch políčok v jednom z ”bielych rohov“, t. j. do rohového bieleho a do dvoch susedných čiernych políčok, ale napíše ich do všetkých ostatných 31 bielych políčok a zvyšok do akýchkoľvek čiernych políčok (okrem spomenutých dvoch). Na bielych políčkach je teda nepárny počet krížikov a na čiernych párny počet krížikov. Okolo každého čierneho políčka s krížikom sú všetky biele políčka tiež s krížikom, preto každá kocka, ktorá zakrýva čierne políčko s krížikom, zakrýva dva krížiky. Iné kocky dva krížiky nezakrývajú. Preto opäť vyhrá Simona.

Ak \(k = 63\), dva krížiky nie sú iba pod jedinou kockou, preto v takom prípade vyhrá Lenka, a to bez potreby akejkoľvek stratégie.
Odpoveď. Pre každé \(0 \leq k \leq 64\), \(k \neq 63\), má vyhrávajúcu stratégiu Simona, pri \(k = 63\) vyhráva automaticky Lenka.