Suppose our two player game consists of them constructing a binary sequence (0’s and 1’s) by taking alternate turns choosing to write either zero or one at each turn, and thereby extending the sequence by one at each turn.
Before the game begins, we are given a number $n$. The game continues until some block of $n$ consecutive digits is encountered for the second time (the two occurrences of the block may overlap). The player that completes this second/duplicate block loses.
Clearly this game is finite as a simplistic bound of $2^n+n-1$ on the number of digits in the sequence suffices as a proof by pigenholeing
If $n$ is odd, how does one prove that the second player (the player who writes the second number in the sequence) has a winning strategy irrespective of what the first player does? Is some kind of strategy stealing argument applicable here?
Best Answer
Let $n$ be odd and let $s_t \in \{0,1\}$ be the $t^{th}$ binaray digit selected. The odd number index $t$ denotes player $1$'s turn and even index $t$ is player $2$'s turn. If player $2$ uses the strategy:
$$s_{q} = 1-s_{q-1} \qquad (\star)$$
for every even $q$ then player $2$ will win. To show this, let $j$ be the smallest number where $s_{i}s_{i+1}\dots s_{i+n-1}$ is the first occurance of a block of $n$ digits with corresponding second occurrence $s_{j}s_{j+1}\dots s_{j+n-1}$.
First, notice that if $j$ is odd then player $1$ loses. Therefore, we will show if $j$ is even we will have a contradiction.
If $j$ is even and $i$ is even then the sequence $s_{i-1}s_{i}\dots s_{i+n-2}$ and $s_{j-1}s_{j}\dots s_{j+n-2}$ are the same because $s_{j} = s_{i}$ and strategy ($\star$) implies that $s_{j-1}=s_{i-1}$. This contradicts the fact that $j$ is the smallest number where we have a block encountered for a second time.
If $j$ is even and $i$ is odd then, \begin{align} s_{j} &= 1-s_{j-1} &&= s_{i} \\ s_{j+1} &= &&= s_{i+1} = 1-s_{i} \\ s_{j+2} &= 1-s_{j+1} &&= s_{i+2} \\ s_{j+3} &= &&= s_{i+3} = 1-s_{i+2} \\ s_{j+4} &= 1-s_{j+3} &&= s_{i+4} \\ \vdots \end{align} Notice that $s_{j+4} = 1-s_{j+3} = 1-s_{i+3} = 1-(1-s_{i+2}) = s_{i+2} = s_{j+2}$ and similarly, $s_{i+5} = 1-s_{i+4} = 1-s_{j+4} = 1-(1-s_{j+3}) = s_{j+3} = s_{i+3}$. Following this pattern it can be shown that $s_{j}=s_{j+2}=s_{j+4}= \dots = s_{j+n}$ and $s_{i+1}=s_{i+3}=s_{i+5}= \dots = s_{i+n-1}$. Since $s_{i+1}=1-s_{i} = 1-s_{j}$ this implies that $s_{j}s_{j+1}\dots s_{j+n-1}$ is alternating $0$'s and $1$'s, i.e., $010101\dots$ or $101010\dots$.
Without loss of generality assume that $s_{i} = 1$. Since $n$ is odd we know $s_{i+n-1}=1$ and by $(\star)$ we know that $s_{i+n} = 0$. Additionally, we know that $s_{j} = 1$ and by $(\star)$ we know that $s_{j-1}=0$. Notice though that $s_{i+1}s_{i+2}\dots s_{i+n}$ is the same as $s_{j-1}s_{j}\dots s_{j+n-2}$. If $j-1 \neq i+1$ then this contradicts the fact that $j$ is the smallest number where we have a block encountered for a second time. If $i+1=j-1$ then $s_{i}\dots s_{i+n-1}$ is the same as $s_{i+2}\dots s_{i+n+1}$ and player $1$ loses.
Therefore, $s_{q} = 1-s_{q-1}$ for all even $q$ is the winning strategy when $n$ is odd.