Aritmetická postupová hra - Arithmetic progression game - Wikipedia

The aritmetická postupová hra je poziční hra kde dva hráči střídavě vybírají čísla a snaží se obsadit kompletní aritmetický postup dané velikosti.

Hra je parametrizována dvěma celými čísly n > k. Herní plán je sada {1, ...,n}. Výherní sady jsou všechny aritmetické průběhy délky k. V Hra Maker-Breaker varianta, první hráč (Maker) vyhraje obsazením a k- aritmetický postup délky, jinak vyhrává druhý hráč (Breaker).

Tato hra se také nazývá hra van der Waerden,^[1] pojmenoval podle Van der Waerdenova věta. Říká se, že pro všechny k, existuje nějaké celé číslo Ž(2,k) takový, že pokud celá čísla {1, ..., Ž(2,k)} jsou libovolně rozděleny do dvou sad, potom alespoň jedna sada obsahuje aritmetický postup délky k. To znamená, že pokud ${ displaystyle n geq W (2, k)}$, pak má Maker vítěznou strategii.

Toto tvrzení bohužel není konstruktivní - neukazuje konkrétní strategii pro Maker. Současná horní hranice pro Ž(2,k) je extrémně velká (aktuálně známé hranice jsou: ${ displaystyle 2 ^ {k} / k ^ { varepsilon}$).

Nechat Ž*(2,k) být nejmenší celé číslo, takže Maker má vítěznou strategii. Kývnutí ^[1] to dokazuje ${ displaystyle 2 ^ {k-7k ^ {7/8}}$. Zejména pokud ${ displaystyle k ^ {3} 2 ^ {k-4}$, pak je hra výhrou Makera (i když je mnohem menší než počet, který zaručuje bez remízy).

Reference

Tento hra související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

Tento článek týkající se matematiky je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.