A Remarkable Pair of Sequences

The terms of the two integer sequences below are equal for all ${n}$ such that ${1<n<777{,}451{,}915{,}729{,}368}$ , but equality is violated for this enormous value and, intermittently, for larger values of ${n}$ .

TicTacToe-2-Sequences

Hypercube Tic-Tac-Toe

The simple game of tic-tac-toe, or noughts and crosses, has been generalized in several ways. The number of cells in a row or column may be increased from 3 to some ${n}$ and the game-space may be increased from ${2}$ to ${d}$ dimensions. The objective of each player is to get ${n}$ co-linear cells. The generalized game of ${n^d}$ -tic-tac-toe has been studied to determine strategies for winning or forcing a draw.

Golomb and Hales (2002) analysed the general game and found conditions for the first player to win and for the second to force a draw. Their analysis involved a number

$a_n = \frac{1}{2^{1/n}-1}$

and they found a remarkable property relating to this sequence.

For increasing ${n}$ the power ${2^{1/n}}$ decreases towards ${1}$ and ${a_n}$ becomes large. Writing ${2^{1/n} = \exp[(\log 2)/n]}$ , expanding the exponential and using the binomial theorem, we can write

$\frac{1}{2^{1/n}-1} = \frac{n}{\log 2} - \frac{1}{2} + \frac{1}{12}\frac{\log 2}{n} + O\left(\frac{1}{n^2}\right)$

Omitting terms of order ${O(1/n)}$ , we define

$b_n = \frac{n}{\log 2} - \frac{1}{2}$

Since ${a_n}$ and ${b_n}$ are asymptotically close, we may expect their integer parts to be equal:

$\left[ \frac{1}{2^{1/n}-1}\right] = \left[ \frac{n}{\log 2} - \frac{1}{2} \right]$

It is remarkable that this equation holds true for ${n\ge2}$ until ${n}$ reaches an enormous number, but is then violated intermittently for larger ${n}$ .

How can this happen? We note that both sequences are irrational (for ${n>1}$ ) and we have no reason to expect that ${a_n=b_n}$ for any ${n}$ . However, since they become closer in value with increasing ${n}$ their integer parts are equal for almost all ${n}$ . However, it may happen that the two quantities ${a_n}$ and ${b_n}$ , while very close in value, may fall on opposite sides of an integer so that the above equality fails. Remarkably, the first occasion for which this happens, is the enormous value ${n=777{,}451{,}915{,}729{,}368}$ .

The On-Line Encyclopedia of Integer Sequences (OEIS) has an entry (A129935) for numbers $n$ such that ${ \lceil \frac{2}{ 2^{1/n}-1} \rceil }$ is not equal to ${ \lfloor \frac{2n}{\log 2} \rfloor }$ . The first eight entries are given in Table 1.

TicTacToe-Table1

Artificial Examples

It is easy to construct a pair of sequences with the above properties. We define

$f_1(n) = \frac{n}{N} - \frac{1}{2n}\,, \qquad f_2(n) = \frac{n}{N} + \frac{1}{2n}$

and denote the integer parts of these by

$F_1(n) = \lfloor f_1(n) \rfloor \,,\qquad F_2(n) = \lfloor f_2(n) \rfloor \,.$

It is easy to see from the definition that

$F_1(kN) = k-1 \qquad\mbox{and}\qquad F_2(kN) = k$

while for ${n\ne kN}$ the two quantities are equal. We see a simple graph of ${F_2(n)-F_1(n)}$ for ${N=100}$ in the Figure below (left panel). The points where the difference is 1 are evenly spaced every ${N=100}$ units. This is because the functions ${f_1(n)}$ and ${f_2(n)}$ have rational slopes ${(1/N =1/100)}$ .

TicTacToe-Figs1and2b

To illustrate what happens if the slope of the functions is no longer rational, we set ${N =\pi^4+e \approx 100.127}$ , which is almost certainly an irrational number. The graph of ${F_2(n)-F_1(n)}$ for ${N=\pi^4+e}$ is shown in the Figure above (right panel).

It is clear that if ${N}$ is a very large irrational number, the spikes in the graph, or points where ${F_1(n) \ne F_2(n)}$ , will be few and far between. Of course, one may argue that this example is very artificial, whereas the sequence ${\{a_n\}}$ defined above arises in a “real-world ” context. This suggests that hypercube tic-tac-toe is a real-world issue!

Sources

${\bullet}$ Golomb, Solomon and Alfred Hales, 2002: Hypercube Tic-Tac-Toe. In More Games of No Chance, MSRI Publications, Vol. 42, 2002.

${\bullet}$ OEIS: The On-Line Encyclopedia of Integer Sequences. A129935: Numbers ${n}$ such that ${ \lceil \frac{2}{ 2^{1/n}-1} \rceil }$ is not equal to ${ \lfloor \frac{2n}{\log 2} \rfloor }$ .

ThatsMaths