Consider a binary string consisting of n bits, where n ≥ 1. We are allowed to perform the following operation: we can replace a 1 by a x, and when we do that we must flip the two bits immediately adjacent to it that remain. Thus 1100 becomes 0x10 when we replace the 1 in the middle by a x, and then we get 0xx1 when we replace the new 1. Prove that we can convert a binary string of length n into a string of n x’s (we refer to this as “crossing out” a string) using the above operation if and only if the string has an odd number of 1s.
What would be the best way to start on this? I'm mainly trying to find an induction step
After the first move has been made, the string is effectively cut into two pieces (one of which may be empty), to the left and right of the first x, and there will be no further interaction between these. So by the IH, we will be successful if both pieces have an odd number of $1$'s. This shows, first of all, that we will succeed if the original string had an odd number of $1$'s, by making the first move on the leftmost $1$.
The converse follows in the same style, by discussing separately the various configurations $010$, $011$, $111$ the first move might be applied to.