Thresholds for Tic-Tac-Toe on Finite Affine Spaces
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918518484631552 |
|---|---|
| author | Bastioni, Luca Giannoni, Alessandro Lobillo-Olmedo, Javier |
| author_facet | Bastioni, Luca Giannoni, Alessandro Lobillo-Olmedo, Javier |
| contents | We introduce an affine version of Tic-Tac-Toe played on the finite affine space $\mathbb{F}_q^m$. Two players alternately claim points, and the first player to occupy all points of an affine subspace of dimension $n$ wins. We call this the $(m,n)_q$-game. For fixed $n$ and $q$, we study how the outcome depends on the ambient dimension $m$.
Using strategy stealing and a blocking-set interpretation, we show that every $(m,n)_q$-game is either a first-player win or a draw, and that the property of being a first-player win is monotone in $m$. This yields a threshold $T(n,q)$: the game is a draw for $m<T(n,q)$ and a first-player win for $m\ge T(n,q)$.
We prove that this threshold is finite by applying the affine/vector-space Ramsey theorem of Graham, Leeb and Rothschild, and we obtain general lower bounds from the Erdős-Selfridge criterion for Maker-Breaker games. In the binary case, we give a direct Fourier-analytic argument, combined with an inductive lifting method, which shows that \[ T(n,2)\le 2^{n+1}. \] We also determine several small cases, including $T(1,q)=2$ for $q\in\{2,3,4\}$ and $T(2,2)=4$, and we prove geometric lower bounds from explicit pairing strategies, such as $T(n,q)\ge n+2$ for every $n\ge 2$.
Our results place affine Tic-Tac-Toe at the interface of strong positional games, finite geometry and Ramsey theory for finite affine spaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05455 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Thresholds for Tic-Tac-Toe on Finite Affine Spaces Bastioni, Luca Giannoni, Alessandro Lobillo-Olmedo, Javier Combinatorics 91A46, 05B25, 05D10, 51E20 We introduce an affine version of Tic-Tac-Toe played on the finite affine space $\mathbb{F}_q^m$. Two players alternately claim points, and the first player to occupy all points of an affine subspace of dimension $n$ wins. We call this the $(m,n)_q$-game. For fixed $n$ and $q$, we study how the outcome depends on the ambient dimension $m$. Using strategy stealing and a blocking-set interpretation, we show that every $(m,n)_q$-game is either a first-player win or a draw, and that the property of being a first-player win is monotone in $m$. This yields a threshold $T(n,q)$: the game is a draw for $m<T(n,q)$ and a first-player win for $m\ge T(n,q)$. We prove that this threshold is finite by applying the affine/vector-space Ramsey theorem of Graham, Leeb and Rothschild, and we obtain general lower bounds from the Erdős-Selfridge criterion for Maker-Breaker games. In the binary case, we give a direct Fourier-analytic argument, combined with an inductive lifting method, which shows that \[ T(n,2)\le 2^{n+1}. \] We also determine several small cases, including $T(1,q)=2$ for $q\in\{2,3,4\}$ and $T(2,2)=4$, and we prove geometric lower bounds from explicit pairing strategies, such as $T(n,q)\ge n+2$ for every $n\ge 2$. Our results place affine Tic-Tac-Toe at the interface of strong positional games, finite geometry and Ramsey theory for finite affine spaces. |
| title | Thresholds for Tic-Tac-Toe on Finite Affine Spaces |
| topic | Combinatorics 91A46, 05B25, 05D10, 51E20 |
| url | https://arxiv.org/abs/2605.05455 |