Arytmetyczna gra progresywna

Gra progresji arytmetycznej to gra pozycyjna , w której dwóch graczy na przemian wybiera liczby, próbując zająć cały postęp arytmetyczny o danym rozmiarze.

Gra jest sparametryzowana dwiema liczbami całkowitymi n > k . Plansza do gry to zbiór {1,..., n }. Zwycięskimi zestawami są wszystkie ciągi arytmetyczne o długości k . W gry Maker-Breaker pierwszy gracz (Maker) wygrywa, zajmując postęp arytmetyczny o długości k , w przeciwnym razie wygrywa drugi gracz (Breaker).

Ta gra jest również nazywana grą van der Waerdena , nazwaną na cześć twierdzenia Van der Waerdena . Mówi ona, że ​​dla każdego k istnieje pewna liczba całkowita W (2, k ) taka, że ​​jeśli liczby całkowite {1, ..., W (2, k )} są dowolnie podzielone na dwa zbiory, to co najmniej jeden zbiór zawiera ciąg arytmetyczny o długości k . Oznacza to, że jeśli ${\ Displaystyle n \ geq W (2, k)}$ , to Maker ma zwycięską strategię.

Niestety, to twierdzenie nie jest konstruktywne – nie pokazuje konkretnej strategii dla Makera. Co więcej, obecna górna granica dla W ( 2 , k ) jest niezwykle duża (obecnie znane granice to: ${\ Displaystyle 2 ^ {k }/k^{\varepsilon }<W(2,k)<2^{2^{2^{2^{k+9}}}}} )$ .

Niech W *(2, k ) będzie najmniejszą liczbą całkowitą taką, że Maker ma zwycięską strategię. Beck udowadnia, że ${\ Displaystyle 2 ^ {k-7k ^ {7/8} <W ^ {*} (2 ,k)<k^{3}2^{k-4}}$ . W szczególności, jeśli , $to$ jest wygraną Stwórcy (mimo że jest znacznie -rysować).