2025/09/25 by Cain, John W., Raymond, Ioannis M., Källersjö, Nora C.
#05D15 #91A46 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2509.21494
In the natural generalization of tic-tac-toe to an n × n × n board where n ∈ ℕ, it is known that the first player has a winning strategy if n ≤ 4 and that either player can force a draw if n ≥ 8. The question of whether the first player has a winning strategy if n = 5, 6 or 7 has remained open. Here, we prove that the first player does not have a winning strategy if n = 7. The proof, which is computer-assisted, exploits the fact that the second player's first four moves can always be chosen such that their remaining moves can be automated via a simple pairing strategy. The process of finding the pairing strategy involves reframing the problem in such a way that the goal is to seek a maximal matching in a bipartite graph that represents the tic-tac-toe board after each player has made four moves. We use the Hopcroft-Karp matching algorithm to find such maximal matchings.