Téma t1: Pojďte pane, budeme si hrát

Zadáno v čísle 22.1.

Zadání

V témátku se budeme zabývat jednou hrou pro dva hráče. Představte si, že s kamarádem napíšete na tabuli bílou křídou všechna přirozená čísla (máte dlouhou tabuli a spoustu křídy). Teď se budete střídat; každý si ve svém tahu nejprve vybere jedno bílé číslo na tabuli a vybarví jej červeně. Následně smaže všechna bílá čísla, která můžeme napsat jako součet několika červených (každé můžeme použít vícekrát). Takže pokud jsme v prvním tahu vybarvili trojku, smažeme 6=3+3, 9=3+3+3, … Jestliže si následně protihráč vybere pětku, smaže 8=5+3, 10=5+5, 11=5+3+3, … Ten hráč, který musí vybarvit jedničku, prohrává.

Nás by zajímalo, co všechno o této hře můžeme říct. Tak třeba – musí tato hra někdy skončit, nebo je možné, že si budeme barvit stále nová a nová čísla a nikdy nepřestaneme? Pokud hra vždy musí skončit, můžeme nějak omezit počet jejích tahů? Můžeme říci, že hra vždy skončí za méně než tisíc nebo třeba milion tahů? Pokud hra nemusí vždy skončit, zkuste najít nějaký konkrétní průběh takové hry.

Zkusme nyní jednu konkrétní hru rozebrat. První hráč začne s dvojkou a smaže tak všechna sudá čísla. My si následně vybereme pětku a smažeme tak všechna lichá čísla větší než pět (7=5+2, 9=5+2+2, …). Nyní protihráč vybarví trojku a my jsme prohráli. Trojku jsme si však mohli vybrat místo pětky v minulém tahu, pak by na soupeře rovnou zůstala jenom jednička a vyhráli bychom. Pokud v nějaké pozici můžeme vyhrát nezávisle na tazích soupeře, řekneme, že máme vyhrávající strategii (to je případ pozice poté, co soupeř vybarvil dvojku). Má na začátku nějaký hráč vyhrávající strategii? Pokud ano, jak tato strategie vypadá?

Zabývejte se hrami s konkrétními tahy v úvodu hry. Pro začátek můžete zkusit například pozice, jež vzniknou po vybarvení čísel 4 a 5, popřípadě 4 a 6.

Řešení

Obsah:

Komenář v 3. čísle

Postřehy ke hře (Dr.$^{MM}$ Marian Poljak)

Základní pravidla a poznatky (Dr.$^{MM}$ Petr Šimůnek)

Skončí to někdy? (Doc.$^{MM}$ Dominik Krasula)

Komentář v 4. čísle

Další příspěvky Dr.$^{MM}$ Petra Šimůnka (Dr.$^{MM}$ Petr Šimůnek)

O (ne)konečnosti kombinatorických her, Kolik stavů může mít hra? (Doc.$^{MM}$ Dominik Krasula)

Další poznatky Dr.$^{MM}$ Petra Šimůnka (Dr.$^{MM}$ Petr Šimůnek)

Dr.$^{MM}$ Petr Šimůnek - shrnutí (Dr.$^{MM}$ Petr Šimůnek)


Komentář v 3. čísle

K tématu zatím došlo několik řešení, z nich vynikají ta od Dr.$^{MM}$Mariana Poljaka Mgr.$^{MM}$Petra Šimůnka. Oba dva se ve svém řešení zabývají například hrami s po- čátečními tahy 4 a 5, respektive 4 a 6 nebo tím, zda hra někdy musí skončit, popřípadě za jak dlouho. Zkuste se nad těmito otázkami také zamyslet! Jaká čísla zůstanou na tabuli po vybarvení 4 a 5? A co můžeme říci o sudých a lichých číslech v případě vybarvení 4 a 6? Dr.$^{MM}$Marian Poljak i Mgr.$^{MM}$Petr Šimůnek tvrdí, že hra může trvat libovolně dlouho, – tedy neexistuje nějaké konkrétní číslo (třeba milion) takové, že by počet tahů v každé hře byl menší než toto číslo. Dr.$^{MM}$Marian Poljak však navíc dokazuje, že pokud jsou první dvě vybraná čísla nesoudělná (tedy jejich největší společný dělitel je jedna), tak hra určitě skončí, a myslí si, že obecně hra vždycky musí skončit. Co si o tom myslíte vy? Pokud budeme hrát piškvorky na sešitu s tisícem čtverečků, hra určitě skončí (ať už něčí výhrou, nebo remízou) do tisíce tahů. Jestliže budeme hrát na nekonečném sešitu, hra nikdy skončit nemusí. Třeba (pokud se s protihráčem domluvíme) můžeme symboly postupně kreslit do jedné dlouhé řady, ve které se pořád budou střídat kolečka a křížky (◦ × ◦ × ◦ . . .) – potom k výherní pětici nikdy nedojde. Může existovat nějaká hra pro dva hráče, která může trvat libovolně dlouho, ale vždycky skončí? Mgr.$^{MM}$Petr Šimůnek také navrhl program v Excelu, který umožňuje simulovat různé průběhy hry. Tím se otevírají nové otázky. Jak si po několika tazích uchovat informaci o tom, která čísla ještě zbyla na tabuli, ač jich může být nekonečně mnoho? A jak tuto informaci aktualizovat při následujícím tahu?


Postřehy ke hře (10b)

Dr.$^{MM}$ Marián Poljak

 Začněme zjevným. Bude-li obarveno červeně jedno číslo, smažou se všechny jeho násobky. Co se stane, budou-li obarvena dvě nesoudělná čísla, řekněme a a b? Čísla b, 2b, . . . , ab dávají navzájem různé zbytky po dělení číslem a. (Kdybychom pro spor předpokládali opak, tedy že některá dvě různá čísla, např. kb a lb, dávají stejný zbytek po dělení a, pak musí být číslo (k − l)b dělitelné a, což nelze, jelikož (k − l) je menší než a a čísla ab jsou z předpokladu nesoudělná.) Nyní stačí k číslům b, 2b, . . . , ab (která jdou vytvořit sečtením několika červených béček) přičítat násobky červeného a. Od každého zbytku smažeme všechna vyšší čísla než ab, která dávají po dělení a tento zbytek. A protože máme všechny možné zbytky, smažeme vlastně všechna čísla vyšší než ab.

Budou-li některá dvě červená čísla navzájem nesoudělná, hra je konečná, jelikož nám zbude na tabuli pouze konečně mnoho čísel, která můžeme dále obarvovat/mazat.

Co když čísla ab nebudou nesoudělná? Označme a = dxb = dy, kde d je největší společný dělitel čísel ab a xy jsou navzájem nesoudělná přirozená čísla. Potom jejich sčítáním zřejmě můžeme dostat pouze taková čísla, která jsou násobky d. A všech násobků d větších než největší společný násobek čísel ab (čímž je dxy), můžeme dosáhnout. Důkaz je v podstatě identický s důkazem u nesoudělných ab. Sečtením násobků čísel dxdy dokážeme totiž dosáhnout všech násobků d vyšších než dxy, právě když dovedeme sečtením násobků čísel xy dosáhnout všech čísel vyšších než xy. Celá situace je pouze „vynásobená“ číslem d, tuto úpravu skutečně můžeme považovat za ekvivalentní, přestože poněkud pofidérní. Druhá část této ekvivalence je již dokázaná, proto platí i naše tvrzení. Můžeme tedy vyvodit obecný závěr.

Jsou-li obarvena červeně nějaká dvě čísla ab, jsou také smazána všechna čísla dělitelná největším společným dělitelem ab, která jsou vyšší než nejmenší společný násobek ab.

Nyní zkusme z obecných pozorování přejít ke konkrétním případům, čímž si je také ověříme. 

Uvažujme hru, která začíná obarvením čísel 4 a 5. Z našich tvrzení již víme, že touto volbou smažeme všechna čísla nad 20. Jak bude vypadat zbytek čísel na tabuli? 

$1$ $2$ $3$ ${\color{red}4}$ ${\color{red}5}$ $6$ $7$ $11$

Není těžké si uvědomit, že pokud některý z hráčů obarví jedno z čísel 2 nebo 3, pak prohraje (po obarvení druhého z těchto čísel již na tabuli zbude jen jednička). Dokážeme, že první hráč, který je v tuto chvíli na tahu, má vyhrávající strategii. Nejlepší tah je obarvit jedenáctku. Nechce-li druhý hráč prohrát, musí obarvit jiná čísla než 1,2,3, tedy 6 nebo 7. Ať obarví kterékoliv z nich, první hráč obarví v následujícím tahu to druhé. Potom už druhému hráči nezbývá nic jiného než vybarvit jedno z čísel 2,3 - první hráč samozřejmě opět obarví to druhé z nich a vyhraje.

Co kdyby první dva tahy byly 4, 6? Tentokrát přežije nekonečně mnoho čísel, jelikož jsou čísla 4 a 6 soudělná dvojkou. Situace bude následující:

$1$ $2$ $3$ ${\color{red}4}$ $5$ ${\color{red}6}$ $7$ $9$ $11$ $13$ $15$ $17$ $19$ $21$ $23$ $25$ $27$ $\dots$

Smazání tohoto nepříjemného nekonečna lichých čísel se ujme první hráč hned následujícím tahem, nechce-li obarvit dvojku a zkapat. Může to udělat tak, aby vyhrál? Pokud smaže 5, nepřítel odpoví tahem 7 a vyhraje. Pokud smaže 7, nepřítel odpoví tahem 5 a opět vyhraje. Přestože má první hráč v tuto chvíli nekonečno možností, nachází se v prohrávající situaci. Druhému hráči si totiž stačí popárovat čísla podobným stylem, jako jsme si už „popárovali“ 2, 3 a 5, 7 v tomto případě. Tj. obarví-li nepřítel jedno z nich, já obarvím to druhé a pošlu ho zpátky do prohrávající situace, kam patří. Druhý hráč si může čísla popárovat následujícím způsobem: (5,7), (9,11), (13,15), . . . První hráč si může barvit jak chce, druhý ale bude svými protitahy nadále udržovat sudý počet lichých čísel nad čtyřkou. (Všechny tyto dvojice tahů zajistí, aby byla smazána všechna vyšší čísla než ta právě obarvovaná.) Proto, až umřou všechna lichá čísla větší než 4 a jediná nesmazaná bílá čísla budou 1, 2, 3, ocitne se první hráč na tahu. Ups ˆ_ˆ

Zjistili jsme tedy vlastně, že obarvení čtyřky je pro prvního hráče prohrávající tah!

Zkusme se nyní ještě zamyslet nad tím, jestli hra musí nutně skončit. Předpodládejme, že máme již obarvená čísla a = dxb = dy. Chceme-li obarvit další číslo dělitelné d, bude toto číslo muset být menší než dxy (všechna vyšší taková čísla jsou už smazána). Čísel menších než dxy je ale konečně mnoho. Má-li tedy hra mít vůbec nějaké ambice být nekonečnou, musí v ní jít obarvit nekonečně mnoho čísel větších než dxy. Žádné z těchto čísel ovšem není dělitelné d. Je zřejmé, že dokud jsou všechna červená čísla dělitelná nějakým společným dělitelem větším než 1, zbývá nám na tabuli nekonečně mnoho čísel. V podstatě můžeme říct, že obarvováním čísel větších než dxy tak nějak snižujeme tohoto největšího společného dělitele všech červených čísel. A bude-li se tento největší společný dělitel rovnat jedné, pak už pravděpodobně umíme smazat tolik čísel, že jich zbyde pouze konečný počet. Hra určitě může trvat libovolně dlouho, budeme-li mazat postupně čísla od 420420, tak uděláme 420420 tahů. Myslím si ale, že hra musí po nějakém konečném počtu tahů skončit, i když nemám žádný důkaz (kromě neexaktního hudrání v předchozím odstavci).


Základní pravidla a poznatky (7b)

Dr.$^{MM}$ Petr Šimůnek

V tomto článku se budu věnovat základním pravidlům hry. 

Určitě nic nepokazíme, když si nejprve cvičně zkusíme několik her. Můžeme si všimnout několika věcí: 

  1. Předpokládejme, že nikdo nechce prohrát (oba chtějí vyhrát). 
  2. Druhého hráče donutíme ke škrtnutí 1 tím, že mu škrtneme všechna ostatní čísla. 
  3. Pokud je vyškrtnuta 2 a 3, tak už zbývá pouze 1. 4. 
  4. Pokud tedy druhý hráč škrtne jedno z těchto čísel, my škrtáme to druhé a on pak musí škrtat 1 (a naopak). 
  5. Skutečným cílem hry je tedy donutit druhého hráče ke škrtnutí 2 nebo 3 tím, že mu škrtneme všechna ostatní čísla. 

Je tedy na čase představit si nějakou konkrétní hru, například hru (4, 5) ze zadání (viz obrázek). Na prvním řádku je výchozí situace (všechna čísla), na druhém po vyškrtnutí 4 (po tahu hráče 1) a na třetím je situace po vyškrtnutí čísla 5 (po tahu hráče 2). A nyní má hráč 1 na vybranou ze 3 možností, může škrtnout 6 nebo 7, nebo 11. Po vyškrtnutí prvních dvou čísel nám už pak zbude pouze 1 číslo (1, 2 a 3 nadále nepočítáme). Po škrtnutí čísla 11 nám však zbývají ještě 2 čísla (6 a 7) a jak vidíme, tak hráč číslo 2 nemůže vyškrtnout obě tyto čísla naráz, tudíž tam jedno nechá a to vyškrtne hráč číslo 1 a vyhraje. A jelikož tedy ve 3. tahu (druhém tahu hráče 1) existuje možnost, jak on vyhraje, nebere si tuto možnost, kdy vyhraje a stane se vítězem.

 

Všimněme si však, že pokud škrtneme čísla 4 a 6, tak vyškrtneme všechna sudá čísla (až na 2, ale to nás tak nevzrušuje, vzhledem k tomu, že o číslech 2 a 3 se vlastně vůbec nebavíme). Ale to důležitější je, že nevyškrtnutých čísel je nekonečně mnoho (všechna lichá). To je větší problém a nám pro začátek bude stačit, když se vždy budeme zabývat uzavřenými skupinami. (Tedy zvolíme si nejprve několik čísel na začátek, která budou vyškrtnuta tak, aby byl počet nevyškrtnutých čísel konečný).

Všimněme si rovněž, kdy dostaneme uzavřenou skupinu: Když jsme škrtali 4 a 6, tak jsme ji nedostali, když škrtneme 8 a 4 tak rovněž ne a při 10 a 12 také ne. Ale i tak existuje pouze nějaké největší sudé číslo a ta nakonec vymizí, poté přijdou na řadu lichá. A po zvolení jakéhokoli lichého čísla se nám pak skupina uzavře a jakmile je skupina uzavřená, hra musí skončit. Hra tedy musí skončit, ale nemůžeme říci kdy, počet tahů může být libovolně velký.

A nyní si představme, že jsme právě škrtli poslední číslo a zbývá už pouze 1, 2 a 3. Jsme ve vítězné pozici? Ano! A co když je v této pozici druhý hráč? Vyhrál? Ano! Jsme tedy v nevítězné pozici. A co když jsme v pozici, že všechny naše tahy vedou k vítězným pozicím druhého hráče? Poté jsme také v nevítězné pozici. Pokud ale nějaký z našich tahů vede k nevítězné pozici pozici druhého 14 hráče, tak naše pozice je vítězná! Můžeme se takto například dostat k číslům 6, 7 a 11. A takto samozřejmě můžeme jít dále a dále a dojít tak až k prvnímu tahu. Problém je, že to není nic jednoduchého. Ale vyplývá z toho, že pro jednoho hráče je hra vyhraná. Viz důkaz Ernsta Zermela o tom, že hra dvou hráčů je pro jednoho hráče předem vyhraná.

Všimněme si, že pokud máme opravdu hodně čísel, tak je těžké a zdlouhavé rozhodovat se, která čísla jsou vyškrtnutá. Jak se tedy můžeme snadno rozhodnout? Všimněme si, že pokud právě vyškrtneme nějaké číslo k, tak pokud od čísla, o které se zajímáme, odečteme k, tak na základě toho, jestli je toto číslo vyškrtnuto, nebo ne, můžeme snadno určit, jestli je vyškrtnuté nebo ne. Tak můžeme i snadno zajistit, že nebudeme počítat s čísly, se kterými nemáme.


Skončí to někdy? (5b)

Doc.$^{MM}$ Dominik Krasula

Není-li řečeno jinak, všechna čísla v tomto článku jsou přirozená.

Interval s nejvíce smazanými čísly

Po prvním tahu hry jsme smazali číslo $n$ a všechny jeho násobky. V druhém tahu druhý hráč vybere nějaké číslo $m$. Smažeme jej, všechny jeho násobky a všechna čísla, která lze napsat ve tvaru $k\cdot n+l\cdot m$. Od určitého násobku hodnoty $n$ si můžeme všimnout zajímavé pravidelnosti. Řekněme, že zvolená čísla vedou k smazání čísla ve tvaru $k\cdot n+a$. Potom smažeme i všechna čísla ve tvaru $(k+b)\cdot n+a$. Tedy, pokud je smazané nějaké číslo $č$, tak všechna větší čísla, která mají stejný zbytek po dělení číslem $n$, jako má číslo $č$, budou po smazání $m$ smazána také. Existuje tedy nějaký interval (říkejme mu „finální interval“) mezi dvěma po sobě jdoucími násobky čísla $n$, pro nějž platí, že neexistuje žádný interval mezi dvěma po sobě jdoucími většími násobky $n$, v němž by bylo smazáno více čísel. Samozřejmě pokud je $m>n$, tak se na situaci musíme dívat naopak, mluvíme o intervalech mezi násobky čísla $m$ (obecně mezi násobky největšího z čísel vybraných v tazích hry).

Příklad 1. V prvním tahu bylo smazáno číslo 5 v druhém číslo 4.

Budeme mít tedy intervaly dané násobky čísla 5. V intervalu 10-15 jsou smazána čísla 10, 12, 13, 14, 15. Z toho víme, že v intervalu 15-20 budou smazána alespoň čísla 15, 17, 18, 19, 20. Je to vlastně triviální pozorování, neboť tato čísla vzniknou prostě přičtením pětky k smazaným číslům z intervalu 10-15, jak ale později uvidíme, jedná se o pozorování překvapivě užitečné. Nutno nezapomenout, že čísla, o nichž víme, že budou z intervalu 15-20 smazána, ještě možná nejsou všechna. Víme, že alespoň tato čísla budou smazána. Nevíme však, jestli právě tato čísla. A skutečně tomu tak není. Ještě bude smazáno číslo $16=4\cdot 4$. Z toho už plyne, že v každém dalším intervalu mezi dvěma po sobě jdoucíme násobky pětky už budou smazána všechna čísla. Takže pokud zvolíme čísla 5 a 4 v prvních dvou tazích, hra určitě skončí po konečném počtu tahů, ať už pak budeme hrát jakkoliv. Nicméně existují dvojice prvních tahů, po nichž ještě nedojde k smazání celého finálního intervalu. Je tedy nutno ukázat, že i v těchto případech není možné hru hrát nekonečně dlouho. Než přejdeme dále, chtěl bych zmínit, že jako důkaz by nám stačilo i dokázat, že takové dvojice neexistují. Toto však není pravda, třeba pro dvojici 4 a 6 neexistuje žádný interval mezi dvěma po sobě jdoucími násobky čísla 6, který by byl smazán celý.

Mazání finálního intervalu

Zde máme výhodu, že ve fináním intervalu (15-20) jsou všechny čísla smazána. Za jakých podmínek (obecně) dojde k tomu, že je finální interval celý smazán? Uvědomme si, že pracujeme vlastně v nějaké zbytkové třídě. Z toho je jasné, že celý interval bude smazán, pokud číslo, které bylo v tahu zvoleno je nesoudělné s modulem. Pokud bychom třeba zvolili 4 a 6, máme dvě soudělná čísla, proto nám ve finálním intervalu (6-12) nějaká nesmazaná čísla zbudou a to konkrétně všechna lichá. Co když budou všechna volená čísla vždy soudělná? Potom hra nikdy neskončí. Problémem však je, že stačí jedna dvojice navzájem nesoudělných čísel a celé se nám to zbortí. Nabízí se tedy prohlásit, že otázka Je tato hra nekonečná? je ekvivalentní s Existuje nekonečně velká množina $M$, skládající se z po dvou soudělných přirozených čísel? Ve skutečnosti tyto dvě otázky nejsou ekvivalentní. Nicméně je rozhodně dobré se nad druhou z nich zamyslet. Pokusíme se sestrojit nekonečně velkou množinu přirozených čísel, která jsou po dvou soudělná. Toto není tak těžké najít. Vhodná je třeba množina všech sudých čísel. Jenže dokážeme nekonečně dlouho vybírat sudá čísla? Ve skutečnosti jsme náš problém nijak nevyřešili, jen trochu pozměnili.

Příklad 2. Máme množinu všech sudých čísel. Ale to je jako mít přirozená čísla vynásobena dvěma. Platí tedy, že hra je konečná s přirozenými čísly právě tehdy pokud je konečná, hrajeme-li jí jen se sudými čísly. Abychom tedy mohli ověřit, že budeme moci nekonečně dlouho mazat sudá čísla, musíme ověřit, že původní verze hry je nekonečná.

Abychom tedy ověřili funkčnost řešení (vybírat jen sudá čísla), musíme vědět, jestli je hra konečná. Ale to je přeco to, co se snažíme najít, toto nám tedy moc nepomůže. Chceme najít nějaké řešení takové, že k ověření jeho správnosti nepotřebujeme vědět, zda je hra konečná. Proto řešení vybírat sudá čísla zavrhneme. Umíme jej ověřit jen tehdy, když víme odpověď a pokud už odpověď víme, tak jej nebudeme potřebovat. Rozhodně tedy chceme, aby pro naši podmnožinu platilo, že když všechny její členy vydělíme největším společným dělitelem (v příkladu s množinou všech sudých čísel je to dvojka), tak bude pořád po dvou nesoudělná. Úkol si můžeme tedy zjednodušit tak, že si zadáme podmínku, aby největší společný dělitel všech prvků byl 1.

Plán důkazu

Výše jsme slibovali, že prodiskutujeme jestli otázka hledání množiny $M$ a otázka konečnosti hry jsou ekvivalentní. Teď už je zřejmé, že nejsou. Máme ale také novou omezující podmínku a to, že největší společný dělitel všech prvků množiny musí být 1. Pokud chceme docílit, aby prvky této množiny šly vybírat tak, že se nestane, že množinu „vyčerpáme“, je toto podmínka nutná. Plán důkazu je následující. Budeme postupně odvozovat další nutné podmínky, jež musí množina nutně splňovat, aby její existence implikovala existenci nekonečně dlouhé posloupnosti tahů ve hře. Cílem je mít natolik „drsné“ podmínky, že je nebude moci splnit žádná množina. Tím dokážeme, že hra je konečná. 

Nekonečné podmnožiny a jejich společní dělitelé

 Chceme tedy mít po dvou soudělnou nekonečnou množinu, kde největší společný dělitel všech jejích členů je 1. Předpokládejme, že existuje nějaký prvek $P$ z nekonečné množiny $M$, který má s nekonečnou podmnožinou této množiny $M$ společného dělitele $A$, který je větší než jedna. Máme tedy množinu $M$ a tu jsme rozdělili na tři podmnožiny. Jedna obsahuje pouze prvek $P$, druhá je nekonečná, pojmenovaná $N$ a třetí, která může, ale nemusí být nekonečná a říkáme jí $K$. Platí, že společný dělitel prvku $P$ a libovolného prvku množiny $N$ je $A$. Máme tedy prvek $P$ a jeho dělitel $A$, který je dělitelem všech čísel nekonečné podmnožiny $N$. Tedy máme nekonečně velkou podmnožinu, kde společný dělitel všech prvků je větší než 1. Jak už jsme říkali, toto je nepřípustné, neboť jsme se opět vrátili k původnímu problému. Samozřejmě v množině $M$ je ještě podmnožina $K$, ale ta je buď konečná, takže možnost vybírat prvky z ní nám nekonečnost hry nezajistí, nebo je nekonečná, ale to potom opět čelíme stejnému problému jako s množinou $M$ a to Dokážeme její prvky postupně vybírat? Je největší společný dělitel všech členů 1? Z toho plyne, že chceme, aby každá podmnožina množiny $M$, která má společný dělitel všech prvků větší než 1, byla konečná. Neboť pokud je taková množina nekonečná, nikam nás to nevede, vyvstává problém isomorfní s problémem původním.

Rozdělení množiny na konečné podmnožiny

Takže mějme opět nějaký prvek $P$ z množiny $M$. Nesmí existovat nekonečná podmnožina množiny $M$, jejíž všechny prvky mají s prvkem $A$ nějaký společný dělitel větší než 1. Nyní si vezmeme množinu dělitelů čísla $P$. Rozdělíme množinu $P$ na disjunktní konečné podmnožiny takové, že v každé této podmnožině mají všechna čísla společný dělitel větší než 1 ( u konečných množin nám toto nevadí), který je zároveň dělitelem $P$. Dále platí, že žádné dvě podmnožiny nemají tento společný dělitel stejný, neboť pokud by byl stejný, tak by to podle našeho rozdělení nebyly dvě podmnožiny, ale jen jedna. Počet podmnožin je nekonečný, neboť rozdělujeme nekonečnou množinu na konečné podmnožiny. Ještě se zbývá zeptat, zdali takový prvek $P$ skutečně musí existovat. A ano musí, neboť podle našich podmínek na množinu $M$ je každá dvojice prvků soudělná, tedy jakýkoliv prvek množiny a prvek $P$ mají největšího společného dělitele většího než 1. Co nám z existence tohoto rozdělení množiny $M$ na podmnožiny vyplývá? Existuje nekonečně mnoho podmnožin, každá z nich má nějaký jiný společný dělitel (všech svých prvků) a tento společný dělitel je zároveň dělitelem $P$. Z toho plyne, že přirozené číslo $P$ musí mít nekonečně mnoho dělitelů.

Když tedy dokážeme, že každé přirozené číslo má konečný počet dělitelů, tak jsme dokázali, že hra musí skončit po konečně mnoha tazích. Neboť jsme konečně dospěli do sporu. Tvrdíme, že nutná podmnínka pro nekonečnost hry je, že existuje po dvou soudělná nekonečná množina M, pro kterou platí, že největší společný dělitel všech prvků je 1, ale zároveň neexistuje žádná její nekonečná podmnožina taková, že největší společný dělitel všech jejích prvků je větší než 1. Ukázali jsme, že aby taková množina mohla existovat, musí existovat přirozené číslo, které má nekonečně mnoho dělitelů. Jenže jak víme, dělitel čísla musí být neostře menší než číslo samo. Tedy počet dělitelů nemůže být větší než číslo samo a číslo je samozřejmě konečné.

Závěr

P1: Námi zadané podmínky nemohou být žádnou množinou splňeny.

P2: Hra může trvat nekonečně mnoho tahů pouze tehdy, existuje-li množina, která splňuje tyto podmínky.

C: Hra nemůže trvat nekonečně dlouho. Jendá se o konečnou hru.

Omezenost?

Když víme, že hra vždy skončí po konečném počtu tahů, vyvstává otázka: Je tento počet tahů nějak zhora omezen? Tedy existuje nějaké číslo $N$ takové, že ať je hra hrána jakkoliv, skončí za méně než $N$ tahů? Odpověď je ne. Ukážeme si příklad hry, která trvá více než $N$ tahů. Hráč první smaže číslo $2N$ (a jeho násobky). Druhý hráč smaže číslo $2N-1$, to rozhodně zatím není smazáno, protože zatím jsme mazali jen čísla větší než $2N-1$. A takto se pokračuje dál, smaže se $2N-2, 2N-3 \dots N+1,N, N-1, \dots 3,2$ a nakonec 1. Hra tedy měla $2N$ tahů. Ale moha by mít $4N$, $8N\dots$ záleží jen, jaké bychom zvolili první číslo. Hra tedy je konečná, vždy skončí, ale může trvat libovolně dlouho.


Komentář v 4. čísle

Otiskujeme řešení Dr.$^{MM}$Mariana Poljaka a Dr.$^{MM}$Petra Šimůnka. Zatímco se Dr.$^{MM}$Marian Poljak zabýval zejména teoretickými aspekty problému, Dr.$^{MM}$Petr Šimůnek si napsal program, pomocí nějž dokáže simulovat různé průběhy hry. Dokumentace a jeho další postřehy ohledně hry jsou bohužel příliš rozsáhlé, než aby se vešly do tohoto čísla, uvádíme tedy pouze část jeho příspěvku. Stejně tak neuvádíme článek od Doc.$^{MM}$Dominika Krasuly, který dokazuje, že každá hra musí skončit. Všechny tyto příspěvky najdete na webové stránce našeho korespondenč- ního semináře. Petr Šimůnek se také zabývá některými teoretickými otázkami, někdy však jeho argumentace není úplně zjevná. Jsou všechny jeho argumenty korektní? Také se dovolává věty Ernsta Zermela, kterou můžete najít na anglické Wikipedii (https://en.wikipedia.org/wiki/Zermelo’s_theorem_(game_theory)) . Jak tato věta souvisí s naším problémem?

Další příspěvky Dr.$^{MM}$ Petra Šimůnka

Dr.$^{MM}$ Petr Šimůnek je autorem mnohých dalších příspěvků, jež se týkají zejména jeho programů pro analýzu her. Programy i příspěvky naleznete na adrese http://uloz.to/xPENcjoy/petr-simunek-zip.  

O (ne)konečnosti kombinatorických her, Kolik stavů může mít hra? (4b)

Následují dva související příspěvky od Doc.$^{MM}$ Dominika Krasuly, který se zabývá zejména obecnými vlastnostmi her. 

 

O (ne)konečnosti kombinatorických her

Doc.$^{MM}$ Dominik Krasula

Článek se zabývá otázkou Může být hra konečná a zároveň trvat neomezeně dlouho? vznesenou v čísle 22.3 v komentáři k prvnímu tématku. Dále se článek zabývá několika podobnými otázkami týkající se (ne)konečnosti her. Může hra s konečně stavy trvat nekonečně dlouho? Existují hry, která mají nekonečně mnoho různých stavů a přitom trvají vždy konečně dlouho? 

Úvod

Něktřeří řešitelé ($Dr.^{MM}$ Marián Poljak; $Doc.^{MM}$Dominik Krasula) se snažili dokázat, že neexistuje žádná horní hranice omezující délku v tématku diskutované hry, ale zároveň platí, že tato hra je konečná. V komentáři v čísel 22.3 byla vznesena otázka, zda existuje nějaká hra s touto vlastností. Pokud je důkaz někoho z nich správný, tak je odpověď jednoduchá. Pojďme ale předpokládat na chvíli, že v tématku diskutovaná hra tuto vlastnost nemá. Můžeme pak tvrdit, že existuje nějaká hra s těmito vlastnostmi? A pokud ano, jaká? Než dospějeme k odpovědi, podívejme se na jinou otázku. Než na tuto otázku odpovíme, pojďme se nejdříve zamyslet nad tím, jak by hra mohla vypadat. Pokud může trvat libovolně (konečně) dlouho, tak v té hře nemůže být konečný počet stavů. Jinak by prostě hra vždy skončila nejvýše po počtu tahů odpovídajícímu počtu stavů. Vyvstává nám tedy další otázka, či spíše podotázka. Existuje konečná kombinatorická hra, ve které existuje nekonečně mnoho možných stavů? Nejspíš by bylo vhodné nějak definovat stav hry. Jelikož pracujeme s hrami pro dva hráče, kde se hráči střídají v tazích, bude stav hry to, jak hra vypadá poté, co hráč vykoná svůj tah. A tyto stavy mohou být různé (v piškvorkách máme dva symboly, tři symboly, jinak umístěné tři symboly...) nebo stejné (třeba v šachách, když jsou figurky rozmístěny stejně, jako již byly). Důležité je, že nás zajímá aktuální vzhled hry, nikoliv, co bylo předtím. Takže, zda jsou stavy stejné, hodnotíme z pohledu někoho, kdo vůbec neví, jaké tahy byly vykonány. Pokud třeba hrajeme hry s předměty na herní ploše, je stavem aktuální poloha těchto předmětů na herní ploše. Již zmíněné šachy mají konečný počet stavů. Dokonce umíme spočítat celkem dobrý horní odhad. Máme 32 figurek, které umisťujeme na šachovnici, která má 64 polí, a víme, že figurka má navíc možnost být vyřazena. Počet stavů je tedy menší než $65\cdot 64\cdot 63\cdot 52 \dots 33$. Jedná se jen o horní odhad, ve skutečnosti to bude míň, protože některé figurky nerozlišujeme a některé mají omezený počet pozic na kterých mohou být a nemůžeme uvažovat situaci, kdy jsou oba králové mimo hru. Jaká hra má nekonečně mnoho stavů? Třeba právě v tématku diskutovaná hra. Máme nekonečně mnoho čísel a v prvním tahu odebíráme libovoné z nich. Takže existuje nekonečně mnohu stavů, ve kterých může hra po prvním tahu být. Rovněž v piškvorkách na nekonečně velké hrací ploše existuje nekonečně mnoho stavů, nekonečně mnoho možných rozmístění symbolů. Nyní již můžeme přejít k zodpovídání otázky. Ukáži vám jednoduchou hru, za jejíž objevení vděčím Vladimíru Sedláčkovi.

Hra 1. Hru hrají dva hráči. První hráč řekne přirozené číslo. A druhý hráč vyhrál.

Je to trochu hloupá hra. Nicméně má hezké vlastnosti. Je to konečná hra, dokonce umíme stanovit po kolika tazích skončí. Po dvou. Navíc v této hře existuje nekonečně mnoho možných stavů, neboť první hráč má na výběr z nekonečně mnoha čísel. No dobrá je to hloupá hra. Zkusme nějakou lepší. 

Hra 2. První hráč řekne číslo. Druhý poté taky řekne číslo. Vyhrál ten, kdo řekl větší číslo.

To už je hra, kterou některé děti skutečně hrají. A od té doby, co máme teorii množin, začíná tato hra být celkem zajímavá... Obecně, chceme-li hledat konečnou hru s nekonečně mnoha stavy, hledáme nějakou hru, kde vybíráme konečně mnoho prvků z nekonečné množiny. A někdy to jsou i celkem složité hry.

Hra 3. Mějme třeba mřížku 5$\cdot$5. Dva hráči postupně do políček zapisují čísla. Na konci se sečtou hodnoty v řádcích, sloupcích, a součet hodnot v obou diagonál. Máme tedy 11 čísel. Pokud je více z nich lichých, vyhrál první hráč. Pokud více z nich sudých, vyhrál druhý hráč.

Dokonce víme, že konečných her s nekonečně mnoha stavy je nekonečně mnoho. Třeba variace předešlé hry, kdy zakážeme použít nějaké číslo. Jsou to jiné hry! Nemysím si sice, že zákaz použít číslo 348 644 849 by nějak zásadně ovlivnil strategie jednotlivých hráčů, ale hry jsou to jiné. Existuje konečná libovolně dlouhá kombinatorická hra, ve které existuje nekonečně mnoho možných stavů? Všechny tři ukázané hry jsou sice konečné, ale nejsou libovolně dlouhé. Existuje pro ně číslo $N$ takové, že ať hráči hrají jakkoliv, hra určitě po $N$ tazích skončí. Pokusme se nyní najít takovou hru, kde takové číslo $N$ nenajdeme. Než k tomu přejdeme, ukážeme si variaci třetí hry.

Hra 31. Máme hromádku pěti kamínků a mřížku 5$\cdot$5. Hráči do políček mřížky umisťují čísla jako ve hře 3, rovněž způsob vyhodnocování hry je stejný. Kromě možnosti zapsat číslo může hráč odstranit kamínek ze hry (ať už je na hracím poli, či ještě v hromádce). Dále může hráč vzít jeden kamínek z hromádky (je-li tam nějaký) a položit jej na políčko mřížky (pokud na něm není žádný kamínek). Tento kamínek dělá překážku ve mřížce. Políčko s ním nemá samo o sobě hodnotu (chová se, jako by na něm nebylo zapsáno žádné číslo). A řádek, na němž leží, rozdělí na dva řádky (pokud je kamínek na okraji mřížky, tak pouze odebírá políčko z řádku, nevzniká řádek nulové délky). Sloupec, na němž leží, rozdělí na dva sloupce. Pokud leží na diagonále, diagonála se do finálního součtu nezapočítává. Hra končí, pokud se zaplní celá mřížka (čísly nebo kamínky). 

Tato hra má samozřejmě pořád omezený počet tahů. Nechť $N$ je počet kamínků a $M$ je počet políček mřížky. Potom počet tahů je $3N+M$ v uvedeném případě je to tedy 40 tahů nejvýše. Proč? Protože umístíme $M$ čísel. Pak můžeme umístit až $N$ kamínků. Ale těchto $N$ kamínků můžeme odebrat a pak musíme zapsat číslo na těch $N$ políček, kde číslo zmizelo kvůli kamínku. Mimochodem víme i dolní odhad a ten je $M$. Musíme zaplnit $M$ políček mřížky. A pokud položíme kamínky na prázdná políčka mřížky, tak pro kamínky neděláme žádné extra tahy. 

Hra 32. Opět máme čtvercovou mřížku 5$\cdot$5, do níž zapisujeme přirozená čísla (a způsob vyhodnocování je jako ve hře 31). V hromádce není žádný kamínek. Jakmile nějaký hráč zapíše číslo do středu mřížky, objeví se v hromádce počet kamínků rovný tomuto číslu ve středu mřížky. Dále se hra hraje jako hra 31, akorát s tím rozdílem, že není možno položit kamínek do středu mřížky.

Předpokládejme, že existuje nějaké $K$, které je horní hranicí počtu tahů, které mohou být ve hře zahrány. Nyní první hráč napíše do středu mřížky číslo $K$. V hromdádce se zjeví $K$ kamínků. Tato hra tedy může trvat až $25+3K$. To je více než horní limit počtu tahů. Předpoklad, že hra trvá nějaký omezený počet tahů, vede ke sporu. Hra může trvat libovolně dlouho, ale je vždy konečná. Neboť vždy trvá nějvýše $25+3K$ tahů, kde $K$ je nějaké přirozené číslo (které je zapsáno ve středu mřížky). Existuje nekonečná hra, ve které existuje jen konečně mnoho možných stavů? Na naši otázku jsme již zodpověděli, ale pojďme se podívat na otázku podobnou, někdo by řekl opačnou. Odpověď je vlastně velmi lehká. Vezměme si šachy, dámu, mlýn a podobné hry, kde se táhne figurkami po konečném množství polí. Když budou dva hráči nekonečně dlouho pohybovat opakovaně figurkou na jedno pole, zpátky, na to samé pole, zpátky... Tak hra bude trvat nekonečně dlouho. Tohle nám stejně jako v případě hry 1 může přijít hloupé. Ale nic moc chytřejšího získat nemůžeme. Máme jen konečně mnoho možných stavů ve hře. Takže abychom dosáhli nekonečně mnoha tahů, musíme tyto stavy opakovat. Minimálně jeden musíme zopakovat nekonečně mnohokrát. V podstatě můžeme jen dělat větší cykly, tedy nehýbat figurkou sem a tak, ale opakovat třeba deset tahů, sto. Můžeme to postupně střídat. Ono pokud sekvencím dovolíme libovolnou konečnou délku, tak jich je nekonečně mnoho (neboť máme nekonečně mnoho možných délek sekvencí), takže mohou existovat hry, kde ono opakování tahů bude vypadat méně hloupě. Ale jinak se vlastně nic nemění. 

 

Kolik stavů může mít hra?

Dr.$^{MM}$ Dominik Krasula

Hvězdičkou značím věci, které v článku nedokazuji, nejsou zjevné, ale dokazoval jsem je ve svém prvním článku k tématku.

Hráči se ve hře střídají. Po každém tahu zbude nějaká podmnožina přirozených čísel stále nesmazána. Může nastat nespočetně mnoho různých těchto stavů, nebo jich může být jen spočetně mnoho? Článek se snaží zodpovědět tuto otázku pro hru z prvního tématka, ale i pro jiné kombinatorické hry.

Jak moc je hra pestrá? Rozhodně může nastat nekonečně mnoho různých stavů. Už po prvním kole může nastat nekonečně různých stavů. První hráč může totiž smazat dvojku, nebo trojku, nebo čtyřku, nebo pětku... Nicméně máme různě velká nekonečna. Víme, že hra má přinejmenším spočetné nekonečno možných stavů. Má jich dokonce nespočetně mnoho? Nabízí se odpovědět ano! Protože po $n$-tém tahu hra vypadá tak, že některá čísla jsou smazána, některá ne. Tudíž stav hry je vlastně podmnožina přirozených čísel. No a množina podmnožin přirozených čísel je nespočetná. Jenže my víme, že ne všechny situace mohou nastat. Například situace, kdy je dvojka smazána, ale čtyřka ne, rozhodně nenastane. Nabízí se tedy otázka, kolik je těchto nepovolených stavů. My se ale budeme spíše ptát na to, kolik je povolených stavů? Jakmile jednou zvolíme dvě nesoudělná čísla, ve hře už zbude jen konečný počet čísel*. Po nějakém tahu $N$ tedy zbude jen konečně mnoho čísel. Jelikož je hra konečná*, je i $N$ konečné. Takže $N$-krát volíme ze spočetného nekonečna čísel. Nyní můžeme počítat. V prvním tahu máme na volbu spočetné nekonečno tahů. Počet možných stavů po prvním tahu je tedy také spočetné nekonečno. V druhém tahu máme také spočetné nekonečno možností, takže počet stavů, jež mohou nastat po druhém tahu je taky spočetné nekonečno. Takto pokračujeme dále. V průběhu prvních $N$ tahů se hra může dostat jen do spočetného počtu různých stavů. No a po $N$ tém tahu už zbývá jen konečně mnoho čísel. Takže do konce hry, ať hrajeme jakkoliv, může od tahu $N$ nastat jen konečně mnnoho různých stavů. Nicméně $N$ může být libovolně velké. Vadí nám to nějak? Popravdě ne. My víme, že po konečném počtu tahů dojdeme do $N$. Takže prostě libovolně dllouho, ale stále konečněkrát, vybíráme ze spočetné množiny. Nicméně toto by chtělo dokázat nějak přesvědčivěji. Pokusíme se možné stavy očíslovat. Pokud to zvládneme, víme, že možných stavů je spočetně mnoho. Víme, že když jsme na tahu, tak se nám hra větví. Máme na výběr z nekonečně mnoha možností. Hru si tedy můžeme představit jako strom, který se v mnoha místech větví na spočetně mnoho větví. Na začátku vybereme jednu větev (zahrání dvojky). Potom vybereme druhou větev (táhneme trojku) a poté v první větvi vybereme první podvětev (stav získáný táhnutím dvojky a následně trojky). Potom započneme třetí větev (stav vzniklý zahráním čtverky), poté pokračujeme v druhé větvi (stav vzniklý zahráním trojky a následně dvojky), následně v první větvi započneme novou podvětev (stav vzniklý zahráním dvojky a následně čtyřky) a pokračujeme již v započaté větvi (stav vzniklý zahráním dvojky, trojky a čtyřky). Asi by bylo těžké toto implementovat. Ale princip je celkem jednoduchý. Vždy začneme novou větev a v každé větvi pokročíme o jedna níže. Pokud je to možné, tak pro každou větev začneme jednu novou subvětev. Pro každou subvětev započneme novou větev. Některé stavy započítáme dvakrát (zvolení dvojky a následně trojky je to samé jako zvolení trojky a následně dvojky) ale to nás vlastně netrápí, protože se snažíme dokázat, že stavů je spočetně mnoho. A pokud při započtení všech stavů alespoň jednou a některých i vícekrát dospějeme ke spočetnosti, tak to znamená, že i bez započítání některých stavů víckrát bude počet stavů spočetný. Hra má tedy konečně mnoho stavů. Ale hra, která má nespočetně mnoho stavů, může samozřejmě existovat.

Hra 1. Máme na tabuli všechna přirozená čísla. Hráči se střídají v tazích. Hráč, který je na tahu smaže jedno z čísel. Vyhrává hráč, který smaže číslo 10. Trochu hloupá hra. Ale má nespočetně mnoho stavů. Protože po tazích zbývají podmnožiny množiny $N - \{10\}$ a těchto podmnožin je nespočetně mnoho. Existuje dokonce i konečná hra, která má nespočetně mnoho různých stavů. 

Hra 2. První hráč vybere reálné číslo. Druhý hráč pak vybere nějaké jiné reálné číslo. Kdo vybral větší číslo, vyhrál.

 

Další poznatky Petra Šimůnka

Dr.$^{MM}$ Petr Šimůnek

V tomto příspěvku si ukážeme další ukázky toho, že můj důkaz je skutečně pravdivý a některé další věci které z toho vyplývají. Nakonec také zkusíme aplikovat poznatky na další hry. Abychom si ulehčili výpočty, tak jsem připravil tabulku, kde se nejprve spočítají všechna zbylá čísla do 1000. Poté vezme každé číslo a zkusí ho škrtnout (Ještě malá poznámka k programu: Je zde 1000000+ hodnot k vypočtení a soubor má 7 MB, přesto však výpočet probíhá mnohem rychleji než když jsem měl stejně velký program, který pouze počítal výsledek pro 100 čísel na 10 tahů. (Nyní máme 1000 čísel a 1000 tahů) Odpovědí na tuto otázku je vylepšený algoritmus, který nový program používá, jelikož ten k vypočtení toho jestli je číslo škrtnuté nebo ne potřebuje výrazně méně operací. Navíc tento program počítá více než tisíckrát více údajů.), poté se testuje jestli zmizelo ve všech případech největší číslo. Můžeme zde pěkně vizuálně kontrolovat, jestli můj důkaz opravdu funguje v praxi. Dále je zde vypsáno prvních 1000 čísel a ukázáno názorně jestli jsou vypočtena nebo ne. http://ulozto.cz/xs8K6R7U/22-00-01-11-11-xlsx Abychom si shrnuli celý důkaz: škrtneme 5, druhý hráč škrtne libovolné číslo, které zbývá a uzavírá tím hru na konečný počet tahů (škrtli jsme 2 nesoudělná čísla). A poté, ať škrtneme libovolné číslo n, tak zároveň škrtneme poslední číslo. Jelikož toto číslo vždy škrtneme, tak na něm n nebude závislé. Jelikož výsledek naší hry se nemůže lišit v závislosti na výskytu tohoto čísla. Představme si hry 6, 7, 11 a 6, 7, v obou případech nás bude zajímat, jak je na tom číslo 6 a v obou případech nám zbude pouze 7, tudíž výsledek bude stejný a výsledek škrtnutí čísla 6 tedy není závislý na 11. Tudíž jeho škrtnutím neměníme výsledek předchozích her, tak můžeme svůj tah "zahodit" - tedy postavit druhého hráče do naší pozice, ale zároveň mu sebereme onu možnost zahodit tah. Celé to stojí na tom, že ať škrtneme jakékoliv číslo, tak zároveň přicházíme vždy i o poslední číslo (celou dobu myslíme situaci po 2 tazích (po škrtnutí 5 a n)). Pojďme se podívat, jak vypadá hra po škrtnutí čísla 5. 

Hlavní věc je, že se nám zde objevují "ostrovy čísel" - 1, 2, 3, 4 je ostrov, 6, 7, 8, 9 je ostrov a tyto ostrovy jsou odděleny čísly 5, 10, 15... Na základě toho můžeme všechna čísla dělit na 4 kategorie a to podle toho, na jakém místě se nacházejí ve svém ostrovu - 1. až 4. místo. Pojďme škrtnout nějaké číslo, vezměme n třeba 201. 

Jak vidíme, tak do 200 se s ostrovy nic neděje, ale pak se začnou zmenšovat a největším nevyškrtnutým číslem je 799. (doporučuji, zkusit si to i v přiloženém souboru). Všimněme si, ostrovy se zmenšují postupně, nejprve vypadává z ostrovů 1. číslo, pak 2., pak 3. nakonec 4. A nyní se pojďme podívat na 1. čísla všech ostrovů, všimněme si, že jako první chybí 201, což je naše n. Když se podíváme na 2. číslo, tak jako první chybí 402, což je rovněž 2n. Dále se podívejme na 3. místo ve skupině, tam je první škrtnuté číslo 603 (3n) a nakonec 4. číslo: 804 (4n). Odpověď nacházíme v algoritmu škrtání čísel: "Číslo m je po škrtnutí čísla n škrtnuté pokud m=n nebo m-k je rovněž škrtnuté." Nyní si jen na chvilku představme, že nejprve škrtneme n a poté 5 (vyjde to nastejno). A když škrtneme číslo na libovolném místě v ostrově, poté budou škrtnuty i všechna následující čísla na stejných místech v ostrovech, zároveň ale ne na jiných místech (škrtáme vždy čísla vzdálená od sebe 5, ani více, ani méně). A nyní se opět můžeme vrátit k tomu, že 1. škrtáme číslo 5 a druhé číslo n. Dále se podíváme, jak se nám bude propagovat škrtání do dalších ostrovů. Jak si můžeme všimnout, tak nejprve jsme přišli o 1. číslo v ostrově, poté 2. poté 3. a nakonec 4. To je z toho důvodu, že postupně byla nejmenší čísla o 1, o 2, o 3 a o 4 větší než 0. Číslo skupiny (0, 5, 10...) a měli jsme n2n3n a 4n. Tudíž vždy, když škrtneme 1. číslo z ostrova, tak bude platit předchozí. Nyní si zvolme n=202

Jak vidíme, tak nejprve přicházíme v ostrovech o 2. číslo, pak 4. pak 1. a nakonec 3. n=202, 2n=404, 3n=606, 4n=808. Může nám to přijít trochu nelogické, ale pokud si uvědomíme, že nám pořadí postupně narůstá, tak to máme 2., 4., 6.! a 8.! Jde o to, že se toto pořadí přenáší do dalšího ostrovu, tudíž ve výsledku pak dojdeme k tomu, že postupně ztrácíme 2., 4., 1. a 3. číslo (z tvaru 2, 4, 6, 8, se do 2, 4, 1, 3 dostáváme operací modulo pěti). Pokud se podíváme na data, tak skutečně vše sedí. Dále zkusme n=203: 

Jak vidíme, tak opět ztrácíme v ostrovech 3. 1. 4. 2. číslo (3., 6., 9., 12.) n=203, 2n=406, 3n=609, 4n=812. A pro n=204:

Ztrácíme postupně: 4., 3., 2. a 1. (4., 8., 12., 16.). n=204, 2n=408, 3n=612, 4n=816. Je naprosto logické, že všechny tyto poznatky můžeme aplikovat i na další (všechny) případy. Tudíž když škrtáme 1. číslo z ostrovu, tak to samé (stejný postup propagace škrtání čísel) platí i pro další čísla. Nyní už jen stačí dokázat, že při škrtnutí libovolného čísla škrtáme i poslední číslo. A je to velmi prosté, pokud škrtáme v nějakém předchozím ostrově číslo na stejném místě jako je to poslední, tak je jasné, že bude určitě škrtnuto. Pokud ne, tak nám dokonce pomůže ono číslo, které druhý hráč škrtl při svém druhém tahu, jelikož díky němu dojde opět ke stejné propagaci, ale od čísla které škrtne ve 4. tahu, které povede ke škrtnutí posledního čísla vždy. Poslední číslo bude tedy vždy škrtnuto a tudíž na něm nemůže být žádné číslo závislé. Libovolná hra začínající 5 má tedy vždy alespoň jedno řešení. Hráč číslo 1 má vítěznou strategii. Stejné zákony můžeme aplikovat i na hry začínající prvočísly, nebudu zde vše rozepisovat, jelikož by toho bylo moc, je to zdlouhavé a naprosto stejné jako v předchozím příkladu. Navíc si to můžeme snadno ozkoušet, jestli to platí v přiložené tabulce: pokud zde vyplníme 2 čísla a bude konečný počet čísel (největší číslo menší než 1000), tabulka otestuje, jestli náš důkaz platí i na onu hru (třeba 7, 50...). Určitě už můžeme hned od pohledu říci, že něco podobného bude platit pro všechna prvočísla. Jelikož zde opět vzniknou ostrovy čísel a opět budou platit stejná pravidla. Dále také můžeme důkaz aplikovat i na některé další hry, třeba i ty začínající na 4, (a pokračující něčím nesoudělným (4, 333...)) i když už některé výsledky známe. Nyní si ještě ukážeme vzoreček na výpočet největšího čísla při škrtnutí 2 čísel - nejprve ukážeme, poté odvození. Mějme 2 škrtnutá čísla m a n, řekněme m=5 a n=201, největším číslem bude 799. Můj vzoreček na výpočet největšího čísla je: (m-1)*(n-1)-1. Odvození je schováno v popisu propagace škrtání čísel na určitých místech u 201 to je 1. 2. 3. a 4. a! 5., onu 5 už ale nevidíme, jelikož už je škrtnutá, tudíž zde máme jakoby 4 "periody" - nebo jak to chceme nazývat. Tudíž musíme od 5 odčíst 1 a to samé logicky platí i pro druhé číslo, nakonec musíme odečíst 1, protože takto bychom vypočítali 1. číslo, kdy se obě škrtání potkávají. Tudíž vzoreček je: (m-1)\cdot(n-1)-1 (a platí pro nesoudělná čísla - jak vidíme, tak očividně nebude třeba platit pro 4 a 6).

 

Petr Šimůnek - shrnutí (9b)

Doc.$^{MM}$ Petr Šimůnek

Poslední příspěvky Petra Šimůnka a shrnutí jeho práce můžete najít na adrese https://uloz.to/!skEott513/petrsimunek-zaver-zip