A game out of this world

For a general $a^n$ cube with $b$ marks to win. With coordinates $(x_1, x_2,... x_n)$ , let $\bar{x_i}$ be a unit vector in the $i^{th}$ dimension. Winning lines are multiples of $\sum{k_i*\bar{x_i}}$ , where $k_i = -1, 0,$ or $1$ . Excluding the case where all $k_i = 0$ , as this is a point/stationary line.

If $k_i = 0,$ at the starting point of a winning line $x_i$ can take $a$ values. If $k_i = \pm1,$ $x_i$ can take $a-b+1$ values between within $[1,a-b+1]$ or $[b,a]$ respectively.

There are $2^r*{n \choose r}$ possible vectors with exactly $r$ non-zero $k_i$ , as they can each be $\pm1$ , (excluding $r = 0$ as this is a point not a line).

Hence in total there are $\sum {n \choose r} a^{n-r}[2(a-b+1)]^r$ = $(a + 2(a-b+1))^n - a^n$ .

This counts each line twice, one time in each direction. Hence there are a total of $\frac{(3a-2b+2)^n - a^n}{2}$ possible winning lines.

Plugging in $a = 12, n = 6, b = 5$ , we get $\frac{28^6-12^6}{2} = 239452160$ .

---

Note to author: Question could use numbers such that the answer becomes easily computable without a calculator, eg $a = 10, n = 6, b = 6$ , or something to do with the form of the answer, eg it can be broken into $(7^6 - 3^6)2^{11} = (343 - 27)(343 + 27) 2^{11} = (2^2 * 79)(2*5*37)(2^{11}) = 2^{14}*5*37*79$

Here's how to derive the formula for the general case. Once we have it, just plug all numbers into a calculator for the specific case this problem asked.

Two marks are on a same line if their displacement vector is a multiple of a winning vector (this winning vector is a term I just made up). Now, on a 2-dimensional board, regardless of the size, there are 4 winning vectors: $\left< 1,0 \right> , \left< 0,1 \right> , \left< 1,1 \right> , \left< 1,-1 \right>$ For a 3-dimensional cube, regardless of the size, there are 13 winning vectors. Some of which are: $\left< 0,1,-1 \right> , \left< 1,1,0 \right> , \left< 1,0,-1 \right>$

Note that for the sake of convenience, I'm indicating vector components in pointy brackets instead of $\hat { i } ,\hat { j }$ or $\hat { k }$ terms.

Note that even though $\left< 1,0,-1 \right>$ and $\left< -1,0,1 \right>$ are 2 different vectors but since they are just opposite, they both have the same line of action so they are counted as one winning vector. That makes some sense because a winning line is the same no matter where you count the marks from (up to down, down to up, left to right, right to left, etc.)

So here's a rule of writing winning vectors in any number of dimensions so none of those are the same: the first non-zero component must be $1$ , any component after that can be either $1,0$ or $-1$ . For example $\left< 0,0,1,0,-1,1,0,...,1 \right>$ .

Now we figured out winning vectors, let's put the ${ a }^{ n }$ cube we are playing on in a coordinate system with $n$ number of axes, we can put marks on points with coordinates of non-zero integers up to $a$ . For example $(87,1,9,31,a-500,...,a-1001,a)$ .

We need $b$ marks in a row to win. Let's denote a winning vector as $\overrightarrow { w }$ , point $C$ is a point with coordinates of integers from $0$ to $a$ . We need to put marks in points $C+\overrightarrow { w }$ , $C+2\overrightarrow { w }$ , $C+3\overrightarrow { w }$ , ..., $C+b\overrightarrow { w }$ to win, assuming they are all inside the cube of course. That means all the points I just listed must have non-zero integer coordinates up to $a$ . However, we only need make sure none of $C+\overrightarrow { w }$ 's coordinates is $0$ and none of $C+b\overrightarrow { w }$ 's coordinates is larger than $a$

The hardest part is over, we now know what to do. For every single winning vector, we count how many points it can make a winning line with. I will be brief from now on because the rest isn't hard. In shorts, we will need the binominal theorem and this identity:

${ u }^{ 0 }{ v }^{ m-1 }+{ u }^{ 1 }{ v }^{ m-2 }+{ u }^{ 2 }{ v }^{ m-3 }+...+{ u }^{ m-1 }{ v }^{ 0 }=$ $\frac{{ u }^{ m }-{ v }^{ m }}{u-v}$

Recall we are playing on a ${ a }^{ n }$ board and need $b$ marks in a line.

For winning vectors existing in $n$ dimensions: $\left< 1,....... \right>$ , we have ${ a }^{ 0 }(a-b+1){ (3a-2b+2) }^{ n-1 }$ winning lines

For winning vectors existing in $n-1$ dimensions: $\left< 0,1,....... \right>$ , we have ${ a }^{ 1 }(a-b+1){ { (3a-2b+2) } }^{ n-2 }$ winning lines

For winning vectors existing in $n-2$ dimensions: $\left< 0,0,1,....... \right>$ , we have ${ a }^{ 2 }(a-b+1){ { (3a-2b+2) } }^{ n-3 }$ winning lines

...................................................

For winning vectors existing in $1$ dimension: $\left< 0,0,0,.......,1 \right>$ , we have ${ a }^{ n-1 }(a-b+1){ { (3a-2b+2) } }^{ 0 }$ winning lines

We used binominal theorem for the previous calculations, now add all those terms together using the identity I just gave, we have the final answer:

* On a ${ a }^{ n }$ board that need $b$ marks in a line, there are $\frac { { (3a-2b+2) }^{ n }-{ a }^{ n } }{ 2 }$ winning lines. *

For the question, put in $a=12$ , $n=6$ , $b=5$ , we have $239452160$ winning lines