Winning strategy for a game, solution verification

combinatorial-game-theorydiscrete mathematicsgame theorysolution-verification

Let $n \in \mathbb{N}$. Two players play a game. Both players have to write a $0$ or a $1$ each move. A player loses if his last number created a sequence of length $n$ that already existed (also if both positions overlap). A game for $n=4$ could look like this: $00100001101011110011$ (Player $2$ lost because of $0011$).

I have to show that player $2$ has a winning strategy for uneven $n$.


There are $2^n$ possible sequences. (For $n=1: 0, 1$; for $n = 3: 000, 111, 001, 100, 010, 110, 101, 011; … $)

Player $1$ has to make every uneven move ($1, 3, 5, …$). The first sequence will be created after $n$ moves and player $1$ will always create the first sequence if $n$ is uneven. Every move after that will create another sequence. $2^n$ is even and player $2$ has to make every even move, this means that he will always win.


Is this already enough? I'm not sure about it but I also don't know how to continue. I think that player $2$ always wins if he's doing the opposite of player $1$'s last move. I played a few games against myself with $n=3$ but I don't know how to generalize it, $01011001, 01101001, 01100101$

Best Answer

First, for each $a \in \{0,1\}$ let $\bar{a} = 1+a \pmod 2$ i.e., if $a=1$ then $\bar{a}=0$, and if $a=0$ then $\bar{a}=1$.

We now consider the strategy where the 2nd player picks his bits that is the opposite of Player 1's last move is satisfied [as mentioned in the comments by Gareth Ma].

THM 1 Let $a_1,a_2,\ldots$ be a sequence of bits such that $a_{2k+2}=\bar{a}_{2k+1}$ for each integer $k$. Then let $n$ be an odd integer, and let $N$ be the smallest integer such that there exists an $L<N$ such that the equation $a_{N-i}=a_{L-i}$ for each $i=0,1,\ldots, n-1$. Then $N$ is odd.

Before we establish Thm 1, we first note that Thm 1 will give us what we want. Let $a_1a_2a_3, \ldots$ be the resulting string, where, for each nonnegative integer $k$, the 1st player sets the $2k+1$-th bit $a_{2k+1}$ of the string, and the 2nd player sets the $2k+2$-th bit $a_{2k+2}$ of the string. Then if the 2nd player, for each nonnegative integer $k$, sets $a_{2k+2}=\bar{a}_{2k+1}$, then the 2nd player will end up winning, because a string of length $n$ will be repeated during the 1st player's move [because Thm 1 will give us that $N$ must be odd]. So the 2nd player has a strategy to win the game.

So we next establish Thm 1. Let us suppose that $N$ is even. We consider 2 cases:

Case 1: $L$ is odd. We make the following claim:

Lemma 2 Let us assume that the equations $a_{N-i}=a_{L-i}$ hold for each $i=0,1,\ldots, n-1$ with $N$ is even and $L$ odd, and with $L<N$.

(i) Then with $L'=L+1$ and $N'=N-1$, the equation $a_{N'-i}=a_{L'-i}$ holds for each $i=0,1,\ldots, n-1$.

(ii) $L \not = N-1$ so $L'<N'$.

Proof of Lema 2 To establish Lemma 2, we first note the following: $L-n+1$ is odd, and $L-n+2j+1$ is odd for each integer $j$, whereas $N-n+1$ is even, and $N-n+2j+1$ is even for each integer $j$. Likewise, $L-n$ is even, and and $L-n+2j$ is even for each integer $j$, whereas $N-n$ is odd, and $N-n+2j$ is odd for each integer $j$. We now note the following for each $i$ satisfying $2 \le i < n$ such that $i$ is even [and $N-i$ is even and $L-i$ is odd]: $$a_{N-i}=a_{L-i}=\bar{a}_{L-i+1}=\bar{a}_{N-i+1}=a_{N-i+2} =a_{L-i+2},$$ where the first $=$ comes from the equation $a_{N-i}=a_{L-i}$ for such $i$, the second $=$ comes from the equation $a_{2k+2}=\bar{a}_{2k+1}$ for each integer $k$, the third $=$ comes from the equation $a_{N-i+1}=a_{L-i+1}$ for such $i$, and the third comes from the equation $a_{2k+2}=\bar{a}_{2k+1}$ for each integer $k$, and the fourth comes the equation $a_{N-i+2}=a_{L-i+2}$ for such $i$. So in particular: $$a_{N-i} = a_{L-i+2} \quad {\text{for all even $i$ satisfying $2 \le i<n$}}.$$

For $i=n$: $$a_{N-n} = \bar{a}_{N-n+1}=\bar{a}_{L-n+1} = a_{L-n+2},$$ where the first $=$ comes from the equation $a_{2k+2}=\bar{a}_{2k+1}$ for each integer $k$, the second $=$ comes from the equation $a_{N-i}=a_{L-i}$ for $i=n-1$, and the third $=$ comes from $a_{2k+2}= \bar{a}_{2k+1}$. So in particular, $$a_{N-n}=a_{L-n+2}.$$ This generalizes for each $i$ such that $i$ is odd [and $N-i$ is odd and $L-i$ is even] and $3 \le i < n$: $$a_{N-i} = a_{L-i+2} \quad {\text{for all odd $i$ satisfying $3 \le i<n$}}.$$ Finally, for $i=1$: $$a_{N-1} = \bar{a}_{N} = \bar{a}_L=a_{L+1}.$$

So from the above one can see the following: $$a_{N-i} = a_{L+2-i} \quad {\text{for each $i=1,\ldots n$}} .$$ So then the following holds: $$a_{N-1-i} = a_{L+1-i} \quad {\text{for each $i=0,\ldots n-1$}}.$$ From this (i) of Claim 2 follows.

To see (ii) of Claim 2, note that the equations $L=N-1$ and $a_{2k+2}=\bar{a}_{2k+1}$ for each $k$, together imply $a_N=\bar{a}_L$, which means that the equation $a_{N-i}=a_{L-i}$ could not hold for $L=N-1$ and $i=0$ after all. $\surd$

So Lemma 2 takes care of the case where $L$ is odd, so we finish next by considering the case where $L$ is even.

Case 2: $L$ is even.

Claim 3 Let us assume that the equations $a_{N-i}=a_{L-i}$ hold for each $i=0,1,\ldots, n-1$ with $N$ and $L$ both even, and with $L<N$. Then with $L'=L-1$ and $N'=N-1$, the equations $a_{N'-i}=a_{L'-i}$ hold for each $i=0,1,\ldots, n-1$.

To see Claim 3, it suffices to show that $a_{N-n}=a_{L-n}$. However, note that $N-n+1$ and $L-n+1$ are both even. So $$\bar{a}_{N-n}=a_{N-n+1} =a_{L-n+1} = \bar{a}_{L-n},$$ and thus in particular $a_{N-n} = a_{L-n}$, and so Claim 3 follows. $\surd$

Note that Thm 1 follows immediately from Lemma 2 and Claim 3. $\surd$


Note also that the proof of Claim 3 would not carry through if $n$ were even.