Thresholds for Tic-Tac-Toe on Finite Affine Spaces
Abstract
We study the strong positional game in which two players alternately claim points of $\F_q^m$ and the first to complete an affine $n$-subspace wins.
We distinguish the first winning dimension $\tau(n,q)$ from the eventual winning threshold $T(n,q)$, without assuming monotonicity in $m$.
Affine Ramsey theory proves finiteness, while the Erdős-Selfridge criterion and explicit geometric strategies give lower bounds.
In the binary case, a quantitative form of the classical quotient argument yields $T(n,2)\le2^{n-1}+n$, with a corresponding bound for any number of colors.
A plane-counting recursion gives further multicolor and extremal estimates.
We prove $\tau(2,2)=T(2,2)=4$ and show that every $31$-point subset of $\F_2^6$ contains an affine $3$-subspace.
This gives an elementary proof of the known equality $\AR_2(3;2)=6$ and implies $\tau(3,2)=T(3,2)\in\{5,6\}$.
Previously known planar outcomes are recovered within the same framework.