arXiv Open Access 2021

Chasing the Threshold Bias of the 3-AP Game

Albert Cao Felix Christian Clemen Sean English Xiaojian Li Tatum Schmidt +2 lainnya
Lihat Sumber

Abstrak

In a Maker-Breaker game there are two players, Maker and Breaker, where Maker wins if they create a specified structure while Breaker wins if they prevent Maker from winning indefinitely. A $3$-term arithmetic progression, or $3$-AP, is a sequence of three distinct integers $a, b, c$ such that $b-a = c-b$. The $3$-AP game is a biased Maker-Breaker game played on $[n]$ where every round Breaker selects $q$ unclaimed integers for every Maker's one integer. Maker is trying to select points such that they have a $3$-AP and Breaker is trying to prevent this. The main question of interest is determining the threshold bias $q^*(n)$, that is the minimum value of $q=q(n)$ for which Breaker has a winning strategy. Kusch, Rué, Spiegel and Szabó initially asked this question and proved $\sqrt{n/12-1/6}\leq q^*(n)\leq \sqrt{3n}$. We find new strategies for both Maker and Breaker which improve the existing bounds to \[ (1+o(1))\sqrt{\frac{n}{5.6}} \leq q^*(n) \leq \sqrt{2n} +O(1). \]

Topik & Kata Kunci

Penulis (7)

A

Albert Cao

F

Felix Christian Clemen

S

Sean English

X

Xiaojian Li

T

Tatum Schmidt

L

Leeann Xoubi

W

Weian Yin

Format Sitasi

Cao, A., Clemen, F.C., English, S., Li, X., Schmidt, T., Xoubi, L. et al. (2021). Chasing the Threshold Bias of the 3-AP Game. https://arxiv.org/abs/2109.03083

Akses Cepat

Lihat di Sumber
Informasi Jurnal
Tahun Terbit
2021
Bahasa
en
Sumber Database
arXiv
Akses
Open Access ✓