Úloha 4.u4: Historie tahů piškvorek (4 b)

Zadáno v čísle 24.4.

Řešeno v čísle 24.6.

Zadání

Martin chce naprogramovat hru piškvorky na „piškvorkovnici“ $200\times 200$ políček. A zrovna si láme hlavu nad dílčí úlohou – chce ukládat historii hry, jak šly tahy od začátku po sobě, aby bylo možné vracet partii o libovolný počet tahů zpět.

Každý tah je jednoznačně určen svou $x$-ovou souřadnicí (hodnota 0 až 199), $y$-ovou souřadnicí (hodnota 0 až 199) a typem (buď křížek, nebo kolečko). Protože se hráči pravidelně střídají, tak víme-li číslo tahu, je už jasné, zda to byl křížek, nebo kolečko. Z pravidel piškvorek je pro nás dále důležité vědět, že hra končí, když se na ploše objeví 5 stejných symbolů vedle sebe v libovolném (i šikmém) směru.

Martin nechce plýtvat místem, a proto chce, aby stav hry, ze kterého půjde jednoznačně určit celá historie tahů, byl uložen v poli o velikosti $200\times 200$ bytů (byte má rozsah hodnot 0 až 255).

Jak to má udělat? Pomohou mu jiné číselné soustavy nebo šikovné kódování? Anebo to vůbec nejde?

Řešení

Odpověď zní: Vůbec to nejde.

Důkaz: Potřebujeme vytvořit spodní odhad na počet her a ukázat, že je větší než počet možných obsahů paměti. Pak bude z Dirichletova principu plynout, že nějaká dvojice her musí být v paměti reprezentovaná stejně, a tudíž nepůjde historie hry jednoznačně rozkódovat.

Musíme však být opatrní, abychom počítali opravdu jen hry, které jsou v souladu s pravidly piškvorek. Pokud se totiž objeví 5 stejných symbolů vedle sebe (v libovolném směru), tak hra končí a nesmíme počítat žádná její pokračování. Proto platný spodní odhad vytvoříme tak, že v piškvorkovnici zakážeme každý pátý řádek a každý pátý sloupec. Potom lze do zbytku políček pokládat cokoliv. Střídání hráčů je dáno pravidly, takže jsou hry určeny jen pořadím obsazování povolených políček. Použitelná část piškvorkovnice je veliká $160 \cdot 160 = 25600$ políček, takže počet platných her (historií) je minimálně $25600!$ (započítali jsme jen úplně zaplněná hrací pole bez zakázaných řádků a sloupců, takže to není nejtěsnější spodní odhad, ale bude nám stačit).

Máme tedy $25600!$ různých historií hry a máme k dispozici pole o velikosti $200 \times 200$ bytů, což nám dává $256^{200 \cdot 200}$ různých obsahů paměti. Abychom byli tato obrovská čísla schopni porovnat, tak je zlogaritmujeme (o základu 2). Protože logaritmus je rostoucí funkce, tak se nerovnost zachová. Potřebujeme tedy ukázat, že:

\[ \log _2(25600!) > \log _2(256^{200 \cdot 200}) \]

Nejprve spočítáme pravou stranu, protože je snazší:

\[ \log _2(256^{200 \cdot 200}) = 200 \cdot 200 \cdot \log _2{256} = 40000 \cdot 8 = 320000 \]

Teď pojďme na levou stranu. Mohli bychom například využít silnější verzi Stirlingovy aproximace, ale my si vystačíme s elementárními prostředky. Využijeme definici faktoriálu a pravidlo pro logaritmus součinu.

\[ \log _2(25600!) = \log _2(1) + \log _2(2) + \log _2(3) + \dots + \log _2(25599) + \log _2(25600) \]

Nyní všechny sčítance zaokrouhlíme dolů (stále nám stačí spodní odhad, nepotřebujeme mít přesnou hodnotu). Dostaneme:

\[ \log _2(25600!) \ge 1 \cdot 0 + 2 \cdot 1 + 4 \cdot 2 + 8 \cdot 3 + \dots + 2^{13} \cdot 13 + (25600 - 2^{14} + 1) \cdot 14 \]

Abychom součet nemuseli počítat ručně, tak si odvodíme hezký vzorec pro součet všech členů kromě posledního. Označme:

\[ S(n) = 1 \cdot 0 + 2 \cdot 1 + 4 \cdot 2 + 8 \cdot 3 + \dots + 2^ n \cdot n \]

Nyní od součtu odečteme dvojnásobek stejného součtu posunutého o člen doprava (poslední člen vynecháme):

\[ S(n) - 2 \cdot S(n-1) = \]\[ = 1 \cdot 0 + 2 \cdot (1-0) + 4 \cdot (2-1) + 8 \cdot (3-2) + \dots + 2^ n \cdot (n-(n-1)) = \]\[ = 2 + 4 + 8 + \dots + 2^ n = 2^{n+1} - 2 \]

Z toho můžeme vyjádřit:

\[ S(n) - 2 \cdot (S(n) - n \cdot 2^ n) = 2^{n+1} - 2 \]\[ n \cdot 2^{n+1} - S(n) = 2^{n+1} - 2 \]\[ S(n) = (n-1) \cdot 2^{n+1} + 2 \]

Když odvozený vzorec aplikujeme na náš výraz, dostáváme:

\[ \log _2(25600!) \ge S(13) + (25600 - 2^{14} + 1) \cdot 14 = \]\[ = 12 \cdot 2^{14} + 2 + (25600 - 2^{14} + 1) \cdot 14 = \]\[ = 25600 \cdot 14 - 2 \cdot 2^{14} + 16 = 325648 \]

Když dáme všechno dohromady, dostaneme nerovnost, kterou jsme potřebovali:

\[ \log _2(25600!) \ge 325648 > 320000 = \log _2(256^{200 \cdot 200}) \]\[ 25600! > 256^{200 \cdot 200} \]

Odvodili jsme, že počet platných her je ostře větší než počet možných obsahů paměti, takže jsme dokázali, že pole o velikosti $200 \times 200$ bytů nemůže stačit na uložení historie hry při žádném zakódování.

Q. E. D.

Martin