Take an $n$-dimensional discrete hypercube with side $n$ - i.e., containing $n^{n}$ nodes. Consider all black/white colorings of it. Does such a coloring exist without a full straight line of $n$ identically colored nodes?
As motivation, this can be considered as a multidimensional version of tic-tac-toe or connect four. The board is this $n \times n \times...n$ cube. Players alternate coloring nodes. Is a draw possible?
For $n=2$ the answer is obviously false. Less obviously, for $n=3$ it seems to also be false. Is it true for 4 and beyond?
Edit: to clarify, all diagonals are allowed.
For $n=4$ a draw is possible. A construction is given by Golomb and Hales in the paper Hypercube Tic-Tac-Toe:
This diagram seems mysterious, so let me unpack.
We think of a $4$-dimensional coordinate $(a,b,c,d)$ as giving a coordinate $(a,b)$ on the first $4\times 4$ board above and a coordinate $(c,d)$ on the second $4 \times 4$ board. We label $(a,b,c,d)$ with a $+$ if the product of the signs on the two boards is positive: both are $+$, or both are $-$. Otherwise, we label $(a,b,c,d)$ with a $-$. The claim is that if $+$ and $-$ are the two players' moves, the position is a draw.
To see this, note that a line in the $4$-dimensional grid is the product of:
The first kind of line does not cause a problem because of the key property: all lines in the first board have an even number of $+$'s, and all lines in the second board have an odd number of $+$'s. When you multiply two such lines together, the result will have an odd number of $+$'s as well, and so it can't be $+,+,+,+$ or $-,-,-,-$.
The second kind of line does not cause a problem simply because neither $4\times 4$ board has a winning line, and this doesn't change if you multiply the line by a $+$ or a $-$.
In fact, we can do better. The same "product" idea works if we start with the two $4\times4\times4$ colorings below, giving us a $6$-dimensional $4\times4\times4\times4\times4\times4$ draw. (It can be checked that the two colorings have the same "even" and "odd" properties respectively.) Instead of $+$ and $-$ I've used red and blue in the diagram below.
For every $n$, there is a dimension in which a draw is impossible, by the Hales–Jewett theorem. This theorem shows a stronger statement in two ways: it shows that there is a dimension in which no matter how the grid is colored (not necessarily with equal amounts of each color) there will be not just a line, but a line with nonnegative slope in each coordinate. Upper bounds on the dimension necessary tend to be very large, however.
For $n > 4$, we can get ever-larger, at least exponentially growing, lower bounds on the dimension in which a draw is possible, via the van der Waerden numbers. The van der Waerden $W(2,k)$ is the least integer such that we cannot $2$-color $\{1,2,\dots,W(2,k)\}$ without finding a $k$-term arithmetic progression. So there is a coloring of $\{1,2,\dots,W(2,k)-1\}$ without such a progression. We can use it to construct for $d = \frac{W(2,k)-2}{k-1}$ a draw in a $d$-dimensional hypercube with side $n=2k$, as follows:
Then along every line, there will not just be two colors: along every line, if we take either the first or the second half of that line, then labels along that half will form a $k$-term arithmetic progression, so just that half of the line will include two colors.
For $n=2k+1$, we can extend this same coloring by carefully "inserting" some cells at the center.