等差数列ゲーム

等差数列ゲームは、2 人のプレイヤーが交互に数字を選び、指定されたサイズの 等差数列全体を占めようとする位置ゲームです。

ゲームは 2 つの整数n > kによってパラメータ化されます。ゲームボードは集合 {1,..., n } です。勝利集合は長さkの等差数列すべてです。Maker -Breaker ゲームのバリアントでは、最初のプレイヤー (Maker) が長さkの等差数列を占有して勝利し、そうでない場合は 2 番目のプレイヤー (Breaker) が勝利します。

このゲームはファンデルワールデンゲームとも呼ばれ、^[1]ファンデルワールデンの定理 にちなんで名付けられました。これは、任意のkに対して、整数W (2, k ) が存在し、整数 {1, ..., W (2, k )} を 2 つの集合に任意に分割した場合、少なくとも 1 つの集合に長さkの等差数列が含まれるというものです。つまり、の場合、Maker には勝利戦略があります。 ${\displaystyle n\geq W(2,k)}$

残念ながら、この主張は建設的ではありません。Maker の特定の戦略を示していないからです。さらに、 W (2, k )の現在の上限は非常に大きいです (現在わかっている上限は、すべての に対して次のとおりです)。 ${\displaystyle 2^{k}/k^{\varepsilon }<W(2,k)<2^{2^{2^{2^{2^{k+9}}}}}}$${\displaystyle \epsilon >0}$

W *(2, k ) を、Maker が勝利戦略を持つ最小の整数とします。Beck [ ^{1] は}であることを証明しています。特に、 の場合、ゲームは Maker の勝利となります (引き分けがないことを保証する数よりはるかに小さいにもかかわらず)。 ${\displaystyle 2^{k-7k^{7/8}}<W^{*}(2,k)<k^{3}2^{k-4}}$${\displaystyle k^{3}2^{k-4}$