5
$\begingroup$

Alice and Bob play a game of Tic-Tac-Toe on a grid of size $N \times M$. The rules of this game are the same as the original Tic-Tac-Toe:

  • Alice plays first (white); Bob plays second (black).
  • On each player's turn, they put a piece of their own on an empty cell on the grid.
  • When a player's pieces form a three-in-a-row (horizontally, vertically, or diagonally in either 45-degree direction), the player wins.
  • If no one wins until the entire board is filled up with pieces, the game ends in a draw.

Instead of trying to win, Alice and Bob decided to cooperate towards a draw. How many distinct drawn endgames are possible when $N, M \ge 4$? Two endgames are distinct if the pieces on at least one cell is different. The order in which each piece is placed is not considered.

For example, $3 \times 3$ grid has 16 distinct drawn endgames:

When one side of the grid is 3, the answer is given as OEIS A339631.

$\endgroup$
2
  • $\begingroup$ Is there an elegant solution, or is this basically a computer programming assignment? $\endgroup$ Aug 7, 2023 at 5:48
  • 2
    $\begingroup$ @KrisVanBael This can be solved without programming, unlike when $N=3$. $\endgroup$
    – Bubbler
    Aug 7, 2023 at 5:52

1 Answer 1

6
$\begingroup$

The answer is

18 if M=N=4, 14 if M=4 or N=4 but not both EDIT 8 if M,N>4 and their product is divisible by 4. 4 if M,N both odd and 6 otherwise.

Reasoning:

There can be no 2x2 square of one colour because any containing 3x3 would have to fill all other squares with the other colour which would then win.

    o o .             o o x
    o o .   forces    o o x
    . . .             x x x
 

2x2 squares with three pieces of one colour can only appear at the corners because

    o o .             o o x
    o x .   forces    o x .
    . . .             x . .
 
    o o . .             o o x .
    x o . .   forces    x o o .
    . . . .             . x x x
 
    x o . .             x o x o
    o o . .   forces    o o x x
    . . . .             x x o o
    . . . .             o . . x
 

up to symmetry w.r.t. the diagonal. Such corner pieces can only happen on 4xN or Mx4 boards and can only occur in pairs.

If M,N>4 therefore every 2x2-square must be balanced and there are only 8 viable 3x3 squares namely the rotations and complement of

    o o x
    x x o
    o o x
 

As any sub 3x3 square determines all others (via unique 3x2 or 2x3 overlap with shifted-by-1 locations) 8 is also EDIT: an upper bound for the overall number of solutions. The solutions can be thought of as cuttings from rectangles made entirely from

    x o
    x o
    o x
    o x
 

or its transpose. EDIT: Of those all that are overall balanced or have Alice one up are reachable.

If N=4<M there are 6 additional solutions depending on whether the left end is unbalanced or the right end or both each option coming with its complement. if M=N=4, there are another 4 (top two unbalanced or bottom two unbalanced plus complements)

$\endgroup$
2
  • $\begingroup$ Your answer for N or M = 4 is correct, but the others is not. Hint: Alice and Bob take turns. (Sorry if it's not clear enough in the OP) Also I have to admit that the remaining part may be a bit tedious. $\endgroup$
    – Bubbler
    Aug 7, 2023 at 9:20
  • $\begingroup$ @Bubbler Oops. I hope it is fixed now. $\endgroup$
    – loopy walt
    Aug 7, 2023 at 9:48

Your Answer

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

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