Take the 2-minute tour ×
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.

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|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 at 12:25
    
@MJD Winning Ways (in the edition that I have) has only two volumes. A drawing strategy for $9$-in-a-row is shown in vol. 2, figure 12 on p. 677. By the way, your a fortiori would be hard to justify. Fortunately, the same strategy works for $n$-in-a-row for all $n\ge9.$ That's because it's purely defensive; it blocks the opponent from making $9$-in-a-row, it does not depend on counterattacking by threatening to make one's own $9$-in-a-row. –  bof Apr 19 at 12:37

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.