Flipping k consecutive binary numbers at a time, how many zeros can we attain? Given a sequence of $n$ numbers, all numbers are $1.$ At each step , we will choose any $k$ consecutive numbers and change their states ( $1 -> 0 $ and $0->1$.) Find the maximal number of zeros we can have?
I think the answer to this problem is:
We have $n\equiv s \mod k$, $(0\le s < k)$. If $2s>k$ the answer is:$[\frac{n}{k}]*k+2s-k$
else , the answer is : $[\frac{n}{k}]*k.$
Obviously, the first answer that pops up in our heads is: $[\frac{n}{k}]*k$. From there I give you an example like this:
For example, if $n=18 , k  = 5$ and we currently have $000000000000000111$ then one possible step is:
$000000000000000111 → 000000000000011000$
Hope to get help from everyone. I'm a newbie. Thanks very much!
 A: You are right. Let $s$ be the remainder of division $n\div k$; $0\le s<k$. Then we can reach the state with either $s$ or $k-s$ leftover "ones" but we cannot reach the state with fewer "ones". This leaves us with the minimum number of "ones" equal to $\min(s, k-s)$, which is equivalent to your claim.
First, number the positions of all of the numbers from $0$ to $n-1$. Then:

*

*Let $a_i$ be the parity ($0$ or $1$) of the number of times we flipped the $k$ consecutive numbers at positions $i$ to $i+k-1$. Obviously, $0\le i\le n-k$.

*Let also $c_i$ be the parity ($0$ or $1$) of the times the number at position $i$ got flipped in the end. So, $c_i$ will be $1$ if we ended up with a "zero" at the position $i$, and $0$ otherwise.

All additions of parities in what follows will be $\pmod 2$.
One can easily check that, for every possible remainder $r, 0\le r<k$:
$$a_0+a_1+\ldots+a_{n-k}=c_r+c_{k+r}+c_{2k+r}+\ldots+c_{qk+r}$$
where $qk+r$ is the largest index smaller than $n$, i.e. $q=\left[\frac{n-r-1}{k}\right]$. Namely, $c_r$ will be flipped every time we flip the numbers at positions $0,1,\ldots,r$; $c_{k+r}$ will be flipped every time we flip the numbers at positions $r+1,r+2,\ldots,r+k$, and so on; finally, $c_{qk+r}$ will be flipped every time we flip the numbers at positions $(q-1)k+r+1, (q-1)k+r+2, \ldots, qk+r$.
Now notice that in the equation above, the left-hand side does not depend on $r$, so the right hand takes the same value for all $r$. However, the right-hand side has a different number of terms, depending on $r$. It is either $\left[\frac{n}{k}\right]$ or $\left[\frac{n}{k}\right]+1$. This number of terms will be $\left[\frac{n}{k}\right]+1$ for $r<s$ and $\left[\frac{n}{k}\right]$ for $r\ge s$. The important thing is that those two numbers of terms differ by $1$, and are thus of different parity.
Try it out on $n=18, k=5$: you will get that:
$$\begin{array}{rcl}a_0+a_1+\ldots+a_{13}&=&c_0+c_5+c_{10}+c_{15}\\&=&c_1+c_6+c_{11}+c_{16}\\&=&c_2+c_7+c_{12}+c_{17}\\&=&c_3+c_8+c_{13}\\&=&c_4+c_9+c_{14}\end{array}$$
and all those five sums are equal $\pmod 2$.
Now, we want the biggest possible number of $c_i$'s to be $1$. How can we accommodate for that? Whatever the sum on the left-hand side, the number of terms (depending on $r$ on the right-hand side) will be of the same or of the different parity. If different, all the groups of $c_i$'s in the corresponding  right-hand side must have a zero in them. Again, looking at the example with $n=18, k=5$: the groups on the right-hand side are of size $3$ or $4$. If $a_0+a_1+\ldots+a_{13}=0$, then each group with three terms has to have (at least) one zero in it. If $a_0+a_1+\ldots+a_{13}=1$, then each group with four terms has to have (at least) one zero in it. In our case, we can do with $a_0+a_1+\ldots+a_{13}=0$, and in each of the groups $\{c_3, c_8, c_{13}\}$ and $\{c_4, c_9, c_{14}\}$ there must be at least one zero, or otherwise the equations won't be satisfied.
In the general case, we have $k$ equations, there are $s$ right-hand sides with $\left[\frac{n}{k}\right]+1$ terms, and $k-s$ right-hand sides with $\left[\frac{n}{k}\right]$ terms. Thus, depending on the parity $a_0+a_1+\ldots+a_{n-k}$, in one of those groups of equations we must have at least one $c_i$ in each to be equal to zero. This means that, as a minimum, either $s$ of the $c_i$'s will be zero, or $k-s$ of them will be zero. The corresponding numbers won't be flipped, so you must end up with at least $s$ or at least $k-s$ "ones" left over. $\quad\blacksquare$
A: Let $r<k$ be such that $n = qk + r$ for integer $q$.  The question presents an algorithm for achieving a minimum number $\min(r,k-r)$ of 1's.  We want to show that this is optimal.  To this end, label the positions of the digits $0, 1, \dots, n-1$.  The key point is that any flipping operation flips exactly one digit with label congruent to $i$ for each $i\in\{0,1,\dots,k-1\}$.
There are $q+1$ positions with label congruent mod $k$ to $\{0,1,\dots,r-1\}$, and there are $q$ positions with label congruent to $\{r,\dots,k-1\}$.  If the number of flipping operations, $f$, does not have the same parity as $q+1$, then there must be at least one label congruent to each of $\{0,1,\dots,r-1\}$ whose corresponding digit is 1.  Similarly, if $f$ does not have the same parity as $q$, there must be at least one label congruent to each of $\{r,\dots, k-1\}$ whose digit is 1.  $f$ can't have the same parity as both $q$ and $q+1$, and hence the minimum number of 1's is at least the minimum of $|\{0,1,\dots,r-1\}|=r$ and $|\{r,\dots,k-1\}| = k-r$, as desired.
