What Is Maximum of Minimum of “Score” of Any Binary Array and of Its Difference Array?

Revision en1, by Zaoly, 2023-12-10 11:14:27

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$?

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 Zaoly 2023-12-10 11:14:27 976 Initial revision (published)