Let n 2 be a natural number. We consider the following game. Two players w r i t e a sequence of 0s and 1s. They start with an empty line and...

Let n ≥ 2 be a natural number. We consider the following game. Two players w r i t e a sequence of 0s and 1s. They start with an empty line and alternate their moves. In each move, a player writes 0 or 1 to the end of the current sequence. A player loses if his digit completes a block of n consecutive digits that repeats itself in the sequence for the second time (the two occurrences of the block may overlap). For instance, for n = 4, a sequence produced by such a game may look as follows: 00100001101011110011 (the second player lost by the last move because 0011 is repeated).

(a) Prove that the game always finishes after finitely many steps.

(b) ∗Suppose that n is odd. Prove that the second player (the one who makes the second move) has a winning strategy.

(c) ∗Show that for n = 4, the first player has a winning strategy. Unsolved question: Can you determine who has a winning strategy for some even n > 4?