# Tic-Tac-Toe Games: Exact Values of Infinitely Many Game Numbers

 COMPUTER SCIENCE/DISCRETE MATH, I Topic: Tic-Tac-Toe Games: Exact Values of Infinitely Many Game Numbers Speaker: Jozsef Beck Affiliation: Rutgers University Date: Monday, October 25 Time/Room: 11:15am - 12:15pm/S-101

Ordinary 3-by-3 tic-tac-toe is trivial; the 3-dimensional 4-by-4-by-4 version is interesting but very complicated (first player wins; solved by Patashnik; heavy computer use); and the 5-by-5-by-5 version is already unsolved (expected to be a draw). If even the simplest games are unsolved than how can we determine "infinitely many exact values"? Well, we cheat a little bit: instead of the usual question of who does it first" we study the somewhat easier (but more fundamental) question of what is doable" (but not necessarily first). In general this question is still hopeless, but to my greatest surprise, I could find the exact solutions of infinitely many `natural games". For example, (1) "Clique Game": Playing on a large complete graph, and taking edges, what is the largest complete subgraph that a player can occupy? (2) "2-dimensional arithmetic progression game": Playing on an N-by-N board, what is the largest square lattice that a player can occupy? (3) Multi-dimensional tic-tac-toe, but the "winning sets" are "planes" instead of the usual "lines".