N bits, flip exactly M bits at a time, what is minimum number of operations to get all 0's to all 1's?

Question

Suppose I have n bits, all initially 0. I can flip any m of the bits (does not have to be contiguous) at a time (one operation). How many operations is required? When is it not possible? It seems that the answer is always in [n/m, n/m + 2] when it's possible to do so.

Answer 1

As fleablood commented, this is impossible if $m$ is even and $n$ is odd. I have three claims: (1) this is the only impossible case; (2) if $n \geq 2m$, then it is always possible to do in less than $n/m + 2$ operations when it is possible, and less than $n/m + 1$ if $n$ and $m$ are both even; and (3) if $n$ is even and $m = n-1$ (generalizing Ben Blum-Smith's example from the comments), then it requires exactly $n$ operations.

Proof of (1): This is trivial if $m = n$. Otherwise, we can flip two bits (say, $a$ and $b$) by first flipping $a$ along with $m-1$ others, and then flipping $b$ along with the same $m-1$ others. If we flip two bits at a time, the only obstruction we can run into is having an odd number $n$ of bits to flip to begin with. This problem is easily fixed if $m$ is odd (flip any $m$ bits initially), so the only bad case is when $n$ is odd and $m$ is even.

Proof of (2): Suppose $n \geq 2m$. Then we can modify the two-bit maneuver from above to flip any even number $2k \leq 2m$ of bits in exactly two moves. To do this, just flip $m$ bits first, and then flip another $m$ bits overlapping the previous ones in a set of size $m-k$. To flip all $n$ bits, then, begin by flipping $m$ bits from 0 to 1, and repeat this until the number of 0 bits remaining is an even number $2k \leq 2m$; then flip these as described. This algorithm flips $m-k < m$ bits three times rather than once, so the total number of flips is less than $n + 2m$, so the number of moves is less than $(n + 2m)/m = n/m + 2$.

Moreover, if $n$ and $m$ are both even, then we can even get away with less than $n/m + 1$. The reason is that the number of bits remaining is always even, so we can choose to apply the $2k$-bit maneuver when $m < 2k \leq 2m$, meaning that only $m-k < m/2$ bits are flipped three times, giving fewer than $(n+2(m/2))/m = n/m + 1$ moves in total.

Notice that this fact pins down the exact minimum number of moves needed. If $m$ and $n$ are both even, then the minimum number of moves needed is the unique integer in the range $[n/m, n/m+1)$. If $m$ is odd, then it's the unique integer in the range $[n/m, n/m+2)$ whose parity agrees with the parity of $n$.

Proof of (3): Take $n$ even and $m = n-1$. Then the only possible moves are to flip every bit except the $i$th one, where $1 \leq i \leq n$. By parity concerns, in order to flip every bit, we must do an even number of moves in total. But for every $i$, we must do moves other than the $i$th an odd number of times, because moves other than the $i$th are exactly what flip the $i$th bit. It follows that we must do the $i$th move an odd number of times (hence at least once) for every $i$, meaning that the shortest solution is to do the $i$th move exactly once for every $i$.