Series: Mathematics Colloquium

Date: Thursday, March 21, 2002

Time: 4:30 - 5:30 PM

Place: 102 McAllister Building

Host: Robert Vaughan

Refreshments: 4:00 - 4:30 PM, in 212 McAllister

Speaker: Jozsef Beck, Rutgers University

Title: Tic-Tac-Toe Like Games

Abstract: 

The well-known tic-tac-toe (easy draw game) is played on a 3-by-3
board.  A popular grown-up version is the 3-dimensional 4-by-4-by-4
game, which was analyzed by O. Patashnik in 1977 (first player has a
winning strategy, computer-assisted proof).  What can we say about the
d-dimensional n^d tic-tac-toe (i.e. the d-dimensional unit cube is
divided into n^d equal subcubes) where the "winning sets" are all
possible "n-in-a-row" sets?  What happens when n and d are large
(i.e., there is no chance to performe a brute force case study)?  When
can the first player win?  How long does it take to win?  When can the
second player force a draw?  When can the second player block every
winning set (i.e., force a "strong draw")?  How about other
"tic-tac-toe like games"?  For example, the players alternately occupy
edges of a large complete graph, and that player wins (loses) who
first gets a triangle (all 6 edges of a complete graph on 4 points,
etc.).  Who wins and how?  The most surprising thing is that we can
answer some of these questions!