From: Fred Galvin Subject: Re: 3^n TIC-TAC-TOE question. Date: Mon, 8 Feb 1999 15:07:36 -0600 Newsgroups: rec.games.abstract,sci.math,rec.puzzles Keywords: Hales-Jewett theorem On Mon, 8 Feb 1999, Mark S. Bassett wrote: > I wish I could remember the authors of this theorem, but I can't. > The best I can offer is that you try looking up "the Hayle-Jewett > theorem" as I _think_ that's what its called (and my apologies > to "Hayle" and "Jewett" for not remembering their names). It's the Hales-Jewett theorem. The original paper is A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222-229; or see the book _Ramsey Theory_ (2nd ed.) by Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. ============================================================================== From: Robin Chapman Subject: Re: 3^n TIC-TAC-TOE question. Date: Tue, 09 Feb 1999 08:27:47 +1100 Newsgroups: rec.games.abstract,sci.math,rec.puzzles Mark S. Bassett wrote: > > Bill Taylor wrote: > > > > > > One gets the feeling that in sufficiently many dement... dimensions, > > a 3-line becomes inevitable. > > > > Anyone got any ideas or refs? > > > > I remember studying this at college. There is indeed a theorem to the > effect that > > If you have p players playing tic-tac-toe on a k-dimensional > board of side n, then: > if k is big enough compared to n and p, an n-line is inevitable. > > Normal tic-tac-toe has p = 2, n = 3, and k = 2. I believe you're > right that when k = 3 a 3-line is inevitable, but the point > of the theorem is that even if k = 3 doesn't guarantee a 3-line > some higher value of k will. > > I wish I could remember the authors of this theorem, but I can't. > The best I can offer is that you try looking up "the Hayle-Jewett > theorem" as I _think_ that's what its called (and my apologies > to "Hayle" and "Jewett" for not remembering their names). The Hales-Jewett theorem. For a proof and applications see Graham/Rothschild/Spencer Ramsey Theory (preferably the second edition which has Shelah's remarkable proof). -- Robin Chapman + "Going to the chemist in Department of Mathematics, DICS - Australia can be more Macquarie University + exciting than going to NSW 2109, Australia - a nightclub in Wales." rchapman@mpce.mq.edu.au + Howard Jacobson, http://www.maths.ex.ac.uk/~rjc/rjc.html - In the Land of Oz