Hales–Jewett theorem
In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to be "completely random".
An informal geometric statement of the theorem is that for any positive integers n and c there is a number H such that if the cells of a H-dimensional n×n×n×...×n cube are colored with c colors, there must be one row, column, or certain diagonal (more details below) of length n all of whose cells are the same color. In other words, the higher-dimensional, multi-player, n-in-a-row generalization of game of tic-tac-toe cannot end in a draw, no matter how large n is, no matter how many people c are playing, and no matter which player plays each turn, provided only that it is played on a board of sufficiently high dimension H. By a standard strategy stealing argument, one can thus conclude that if two players alternate, then the first player has a winning strategy when H is sufficiently large, though no practical algorithm for obtaining this strategy is known.
More formally, let WnH be the set of words of length H over an alphabet with n letters; that is, the set of sequences of {1, 2, ..., n} of length H. This set forms the hypercube that is the subject of the theorem. A variable word w(x) over WnH still has length H but includes the special element x in place of at least one of the letters. The words w(1), w(2), ..., w(n) obtained by replacing all instances of the special element x with 1, 2, ..., n, form a combinatorial line in the space WnH; combinatorial lines correspond to rows, columns, and (some of the) diagonals of the hypercube. The Hales–Jewett theorem then states that for given positive integers n and c, there exists a positive integer H, depending on n and c, such that for any partition of WnH into c parts, there is at least one part that contains an entire combinatorial line.
...
Wikipedia