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