2
$\begingroup$

Two players A and B play Tic-Tac-Toe on an infinite 3-dimensional grid. Player A starts first and uses X, player B plays second and uses O. Every time player A places an X on the grid, player B can place $n$ number of O's. Player A wins if he eventually succeeds to make 3 in a row - horizontally or vertically, otherwise the game is a draw. For which values of $n$ player A can always win?

Harder version: What if player A has to make $k>3$ in a row? Partial solutions are welcome, 2-dimensional grid and $k=4$ seems doable. (I think the answer is nice, but don't have a complete solution yet)

Remark: No diagonals here.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

A wins if $n=2$:

No matter what B plays on their first turn, there will be a flat plane passing through the first X, which contains at most one O. A can create a 2 by 2 square on that plane while forcing all of B's moves to block both ends of a 2-in-a-row, and then complete a row of 3.

B draws if $n=3$:

Divide the entire grid into 2x2x2 cubes. Every cell borders exactly three cells in its cube. Whenever A places an X, B places O's in those three cells. This guarantees that A can never have X's in two neighboring cells in the same cube. Every possible line of three includes two neighboring cells in the same cube, so A can't complete a line.

The same argument also shows that B can draw on an $m$-dimensional board with $k=3$ if $n\ge m$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It seems nobody wanted to think about the general case, so I give you the correct answer tag. This is a very nice solution btw, even better than your first one. $\endgroup$
    – Puzzle Prime
    Commented Oct 6, 2015 at 19:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.