### Zaoly's blog

By Zaoly, history, 8 months ago,

A binary array is an array where all elements are either $0$ or $1$.

For any binary array $a_1, a_2, \ldots, a_n$ of length $n$, we can figure out the corresponding unique array $b_1, b_2, \ldots, b_n$ of length $n$ that satisfies $b_1 = a_1$ and $b_i = a_i \oplus a_{i - 1}$ for any $2 \le i \le n$, where $\oplus$ denotes XOR operation. Then count the number of $1$-s in array $a$, count the number of $1$-s in array $b$, and find the minimum of them as the “score” of array $a$.

For example, provided $a = [1, 0, 1, 1, 0, 0]$, then $b = [1, 1, 1, 0, 1, 0]$. The number of $1$-s in array $a$ is $3$, the number of $1$-s in array $b$ is $4$, and the minimum of them is $3$, so the “score” of array $a = [1, 0, 1, 1, 0, 0]$ is $3$.

For any given $n$, what is the maximum “score” of array $a$ among all possible arrays $a$? And how to construct a possible array $a$?

• +10

 » 8 months ago, # | ← Rev. 2 →   0 I believe the answer is $\lceil{\frac{n}{2}}\rceil$
•  » » 8 months ago, # ^ |   0 this can be done with the array, $a = [1, 0, 1, 0, 1, \dots]$
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 I don’t believe so. For $n = 4$, the answer is not $\big\lceil \frac n 2 \big\rceil = 2$ but $3$, because we can construct an array $a = [1, 0, 1, 1]$, where $b = [1, 1, 1, 0]$.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 My bad! Well now we have a lower bound for the answer. Also notice something: for the array $a = [1, 0, 1, 0, \dots], b = [1, 1, 1, 1, \dots]$ If we replace any 0 with a 1 in the array $a$, it will add 1 1 to the array $a$ and remove 2 (or 1) 1 from the array $b$. Hope that helps!
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 But what if we don’t make the values at odd indices $1$? That is, what if we don’t form our array like $a = [1, \texttt{X}, 1, \texttt{X}, \ldots]$? Such as, $a = [1, 1, 0, 0, 1, 1, 0, 0, \ldots]$ — just like when we move some $1$-valued elements to other positions.
•  » » 8 months ago, # ^ |   +3 Ww can get something around $2n/3$ with $a = [1, 1, 0, 1, 1, 0,\dots]$ and $b = [1, 0, 1, 1, 0, 1,\dots]$
 » 8 months ago, # |   0 I bruteforced all possible sequences for $1 \le n \le 12$ and it looks like the maximum score is always $\lfloor \frac{2n+1}{3} \rfloor$. It is not hard to see that this score can be obtained by using the pattern $[1,0,1,1,0,1,1,0,1,\dots]$. Unfortunately I don't know how to prove these claims.
•  » » 8 months ago, # ^ |   0 So am I hahaha
 » 8 months ago, # | ← Rev. 5 →   +10 Consider having $x$ ones in array $a$.First assume that $x \lt \frac{n}{2}$. Then, we can make a prefix of alternating zeros and ones, followed by a bunch of zeros. Then, array $b$ has something like $2x$ ones. Then the score is $\min(x,2x)=x$ (which is less than half $n$).Now let's try $x \gt \frac{n}{2}$. Now, we can make $a$ have an alternating prefix and a suffix full of ones. The length of the alternating prefix is approximately $2n-2x$, so the score is $\min(x, 2n-2x)$, which is maximized when $x=2n-2x$ therefore $\text{score}=x=2n/3$.I'm not being precise with my rounding and so on but you get the idea. Also, i didn't prove that this construction is optimal but it's very intuitive that the amount of ones in $b$ is maximized when we construct $a$ as described (again, sorry for lack of proof)EDIT:We can prove optimality by first proving an upper bound and then showing that my construction achieves it.If there are more zeros than ones in $a$, you can only have at most $2x$ ones in $b$, because that's the amount of adjacent positions there can be next to a one.On the other hand, if there are more ones than zeros in $a$, we are limited by the number of zeros, which is $n-x$, so there can be at most $2(n-x)$ ones in $b$. (same argument as above)Note that the proposed construction reaches both bounds (trivial), so it must be optimal.