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.

$\endgroup$

1 Answer 1

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$.

$\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$ Oct 6, 2015 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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