Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How can be it proved that tic-tac-toe on an infinite grid (winning with $12$ in a row, a column or a diagonal) can always end in a tie (with optimal strategies of both players)?

There is a hint: to use a "magic square of $4\times4$" and a "tessellation".

share|cite|improve this question
    
Tic-tae-toe on an infinite grid can never end in a tie. Presumably you mean that neither player has a winning strategy. – Peter Taylor Apr 15 '14 at 10:39
    
@PeterTaylor I define tie as "not making 12 in a row, a column or a diagonal", so the infinite play is a tie. You are right about the inappropriateness of the verb "end", though. – John Smith Apr 15 '14 at 18:42
2  
There's a proof in one of the later volumes of Winning Ways that the 9-in-a-row game is a draw on an infinite board. A fortiori the 12-in-a-row game is too. – MJD Aug 26 '14 at 14:10
    
@PeterTaylor According to the rules, the game ends after $\omega$ moves if nobody has made $12$ in a row. One could consider a variant, where play continues into the transfinite as long as there are any unoccupied points, but this is not so popular. – bof Apr 19 '15 at 12:25
1  
@GarethRees Yes, I know. I remarked on that fact in my comment to MJD, and again in my reply to your comment, by bolding "If". The only reason for my comment to MJD was that he did not mention the pairing strategy but only reported that "the 9-in-a-row game is a draw", which I thought could be misleading. – bof Apr 28 '15 at 11:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.