# Winning strategy for a game, solution 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$$

• Through computer simulation I can confirm that your strategy is indeed correct for odd $n$ i.e. player $2$ always wins by playing the opposite of player $1$'s move. What is your proof? Apr 18, 2022 at 20:25
• Your strategy is valid. no suppose by contradiction that player 2 can't loose. You have two case : the duplicated word was first ended by player 2 or by player 1. For both cases, find a contradiction. Apr 19, 2022 at 14:40
• Where did you get this problem, @Annabelle99? It was a good one!
– Mike
Apr 19, 2022 at 16:07
• From our discrete math professor ^^, another problem is to color each square of a 7x7 chess board and to prove that there will always be 4 squares of the same color that create the corners of a rectangle; absolutely love my professor :D Apr 19, 2022 at 18:03

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 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.

(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'.

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

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 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. 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.