I was shown this puzzle by @hy3na_xyz, a member of the Rutgers competitive programming discord server. Credit goes to them!

Given an N-dimensional tic-tac-toe board of side length L, how many winning paths are there? A winning path is a sequence of L cells that follow a linear path through the N-dimensional hypercube of the game board.

My first idea was to fix one endpoint of the path and count the number of possible other endpoints that could match with it.

Unfortunately, the number of matching endpoints is not invariant - in a standard 3x3 2d tic-tac-toe board, each corner has 3 possible matching endpoints, whereas the middles of the sides only have 1.

In higher dimensions, there are even more cases: A 3x3x3 3d tic-tac-toe board has separate cases for the corners, middles of edges, and centers of faces, and each has a different number of possible endpoints.

Instead, I rethought what it meant for a path to be a winning path: If a sequence of L points forms a line in the game hypercube, then its points must form an arithmetic sequence in order.

This also means that if we consider each dimension separately, the L points coordinates in such dimension must similarly form an arithmetic sequence.

Consider the following 3x3 board:

3| a b c
2| d e f
1| g h i
 +------
   1 2 3

The sequence abc has coordinates (1, 3) (2, 3) (3, 3). Its x and y coordinate sequences are themselves arithmetic sequences.

How can we use this to count the total number of sequences?

First, let's temporarily consider the sequences as ordered, and then divide by two later on. This makes the computation easier.

Define the X component of a winning path as the sequence created by extracting the X coordinates of all of the points in the path. In our 3x3 example, there are 5 possible X component sequences:

• 1, 1, 1
• 2, 2, 2
• 3, 3, 3


• 1, 2, 3
• 3, 2, 1

We can generalize this: In a hypercube of size L, there are L+2 possible sequences for each dimension.

From this, it looks like our answer is [(L+2)^N]/2 sequences. This is almost correct.

Firstly, it is immediately obvious that (L+2)^N is not always even, so this formula will not always be integral. Recall why we are dividing by 2: we were considering out sequences to be ordered.

(L+2)^N does not exclude sequences such as (1, 2, 3) (1, 2, 3) (1, 2, 3) which consist of L identical points. These are sequences that by nature do not have two endpoints, and so do not have two ordered copies. To fix this, we subtract L^N before dividing by two, as each board point represents one such sequence.

So, our formula is [(L+2)^N - L^N]/2!

---

@hy3na_xyz had an incredibly elegant visual proof.

Consider the standard 3x3 tic-tac-toe board. Nest it inside a 5x5 board like so:

a b c d e
f x x x f
g x x x g
h x x x h
e b c d a

For any given winning path in the 3x3 board, extend its endpoints out into the 5x5. These two cells that it extends outward to correspond uniquely to that winning path.

a b c d e
f x x x f
g x x x g
h x x x h
e b c d a

We can prove this constructively: For any point in the 5x5 board but not in the central 3x3, its paired point must have x and y offsets of either 0 or 4. Because of the size of the board, there will always be only one possible paired point.

a b c d e
f x x x f
g x x x g
h x x x h
e b c d a

This generalizes to higher dimensions and larger boards: Nest the board inside an N-dimensional hypercube of side length L+2. Each winning path will correspond to a pair of two points inside the outer shell.

Note that this formula doesn't hold for L = 1.

---

Thanks again to @hy3na_xyz for this really cool problem & visual proof!

Signing off for now.

tags: math