Computer Science/Discrete Mathematics Seminar I

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".