Halesova–Jewettova věta

Technology

12 hours ago

Author

Halesova-Jewettova věta je důležité tvrzení Ramseyovské teorie, které tvrdí, že

: Pro každá přirozená čísla n a c existuje dostatečně velké D, od kterého lze v každém obarvení nadkrychle strany n a dimenze D c barvami najít stejně vybarvený řádek, sloupec, diagonálu, tělesovou úhlopříčku, či nějakou nadtělesovou úhlopříčku.

Tvrdí tedy, že úplný chaos při barvení není od dostatečně velkých objektů možný, přičemž oním „dostatečně velkým“ se zde myslí „při dostatečně velké dimenzi“.

Aplikace

Piškvorky

Triviálním, ale zajímavým důsledkem je fakt, že pro dostatečně velké D neexistuje v piškvorkách hraných na hyperkrychli dimenze D remíza: tahy tu chápeme jako barvení dvěma barvami, konec hry nastává když jsou všechna místa v nadkrychli obarvena - Hales-Jewett nám pak říká, že se nemohlo stát, že nějaké barva v předchozích tazích neobsadila výherní pozici.

V kombinaci s argumentem o kradení strategie dostáváme tvrzení, že na dostatečně velké nadkrychli má začínající hráč vyhrávací strategii.