Joining digits in binary string Given a binary string of length $k \in \mathbb{N}_+$ find a maximum number of digits you can remove by combining adjacent elements into opposite ones (i.e you can combine 2 adjacent $1$s into $0$ or combine 2 adjacent $0$s into $1$).
What I already got: if a string consists only of characters of 1 type then you can reduce it to a string of length $1$ if and only if $k \not\equiv 0 \ \text{(mod 3)}$. Otherwise, it will become a string of length $2$. (if you recursively start adding new digits starting from a one-digit string you can see that $k \ \text{mod 3}$ is an invariant).
Binary strings seem to be simple structures but even after research, I couldn't find any article about that problem. Thanks in advance!
 A: Let $a$ be the number of ones, and $b$ be the number of zeroes. Note that the quantity $a-b\pmod 3$ is invariant, because each move either decreases $a$ by $2$ and increases $b$ by $1$, or vice versa. This means that if $a-b\equiv 0\pmod 3$, there is no hope of reducing the string to a single character. Furthermore, starting from any string which alternates between $0$'s and $1$'s there is no move at all.
I will show that in the case $a-b\not\equiv 0\pmod 3$, and at least one move is available, then you can reduce the string to a single character. Indeed, we just need to show that we can always make a move which leaves another available move. This is OK because any string which contains $00$ will either contain $001$ or $100$, so you can move on those pair of zeroes to get a pair of ones in the result. The only exception to this rule is the case where the string just consists of $n$ zeroes and no ones. If $n\ge 4$, then moving on two zeroes at an end works. $n=3$ cannot happen because that violates $a-b\not\equiv 0\pmod 3$.
By the same logic, you can show that if $a-b\equiv 0\pmod 3$, and there is at least one move available, then you can reduce the string down to two characters.
