**Motivation:**

Consider a game in which two shooters take turns shooting at a target. The winner is the one who manages to hit the target first. Say each shot has a relatively small chance of hitting the target. What is the fairest way to take turns?

The $0$-$1$ valued *Thue-Morse sequence* valued claims to find an answer. The sequence can be heuristically described as “*taking turns taking turns taking turns...*”. It is defined as follows:

Using $0$ to denote that the first player should shoot and $1$ for the second, the sequence is defined by the following iterative process - start with the string $1$. At each iteration step, append the *binary complement* of the string to the end. By binary complement, I mean the string obtained by turning all $1$’s in the string to $0$’s and $0$’s to $1$’s. Thus the sequence of strings starts as follows:

$1, 10, 1001, 10010110, \dots$

The Thue Morse sequence is the infinite string obtained by iterating this process. The full sequence begins:

$01101001100101101001011001101001 \dots$

Now  I would like to try to quantify the sense in which this is really the fairest turn taking algorithm possible. To this end, consider the following definitions.

**Definitions:**

Define, for each $0$-$1$ valued sequence $\{a_n\}$ the *advantage sequence* $\{Va_n\}$ as follows:

$Va_n := \sum_{i = 0}^{n-1} (-1)^{a_i + 1}$

Thus $Va_n$ records at each step $n$, how many more turns player 1 has had over player 2 or vice versa.

Define now for each $k \geq 1$the *k-th order advantage sequence* $\{V^ka_n\}$ by 

$V^1 a_n := Va_n$,

$V^ka_n  := \sum_{i = 0}^{n-1} V^{k-1}a_i$ for $ k > 1$.

 Intuitively, the $V^k$ can be understood as follows. 

- $V^1a$ records how many more turns player 1 has had (or vice versa) than player 2 thus far.

- $V^2 a$ records how many times (with multiplicity) player 1 has had more turns than player 2 thus far.

- $V^3 a$ records how many times player 1 has had more of a second order advantage than player 2 thus far.

... and so on.

Now, let us define a partial order on the set of $0$-$1$ valued sequences as follows: 

$\{a_n\} ≥ \{b_n\}$ if for all $n \geq 0, k \geq 1$, we have $|V^k a_n| ≥ |V^k b_n|$.

As is customary, we say $\{a_n\} > \{b_n\}$ if $\{a_n\} ≥ \{b_n\}$ but not vice versa.

Now we are ready to state the problem.

> **Problem:** Denote by $\{T_n\}$ the Thue-Morse sequence. Is it true that $\{T_n\} > \{a_n\}$ for any other $0$-$1$ valued sequence $\{a_n\}$ such that $a_0 = 1$? Thus the Thue-Morse sequence would be the unique turn taking sequence that minimises all the higher order advantages.