학술

Thresholds for Tic-Tac-Toe on Finite Affine Spaces

arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.

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.

관련 뉴스