Half from any $2n$ but not $2n+2$ Let $n$ be a positive integer. What is the length of the longest possible sequence of $0$'s and $1$'s such that among any $2n$ consecutive numbers, exactly half are $0$'s, but among any $2n+2$ consecutive, this is not true?
It is possible to have a sequence of length $3n$: $11\dots100\dots011\dots1$. In addition, after the first $2n$ numbers the rest are fixed: the $(2n+i)$th number must be the same as the $i$th number.
 A: Suppose that the initial $2n$ bits are $b_1b_2\ldots b_{2n}$, $n$ of them being $0$ and the other $n$ being $1$. Suppose that we extend this to $3n+1$ bits:
$$b_1b_2\ldots b_{2n}b_{2n+1}\ldots b_{3n}b_{3n+1}=b_1b_2\ldots b_{2n}b_1\ldots b_nb_{n+1}$$
There must be a $k$ such that $1\le k<2n$, and $b_k\ne b_{k+1}$. Now consider the string $\sigma$ of length $2n+2$ starting with $b_k$: the $2n$ bits from $b_{k+1}$ through $b_{k+2n}=b_k$ has $n$ zeroes and $n$ ones, and the additional bits are $b_k$ and $b_{k+1+2n}=b_{k+1}$, which are unequal, so $\sigma$ has $n+1$ zeroes and $n+1$ ones. Thus, $3n$ is the maximum possible.
A: We start with any string $S = a_1a_2\dots a_{2n}$ of $n$ zeros and $n$ ones. 
Then we must have $a_k = a_{2n+k}$. Furthermore, we must have $a_{2n+1} = a_{2n+2}$ or else the first $2n+2$ letters have equal proportion.
We then also must have $a_{2n+2} = a_{2n+3}$ by the same logic, since the substring $a_2 a_3 \dots a_{2n+1}$ has an equal proportion of zeros and ones. In particular, we must have $a_{2n+1}=a_{2n+2}=\dots$. The longest we can have both $a_k = a_{2n+k}$ and this condition is if the first $n$ letters are $1$ (or $0$) and the next $n$ are $0$ (or $1$) and the last $n$ are $1$ (or $0$) again. Hence, $3n$ is the longest sequence.
