This has me stumped. How can you prove that for the alphabet $\Sigma = \{0, 1\}$, any string $w \in \Sigma^\star$ with an equal amount of 0's and 1's will always have either the format $0x1y$ or $1x0y$ (where $x$ and $y$ are substrings also $\in \Sigma^\star $ and have an equal amount of 0's and 1's) ?
I see that $x$ and $y$ can both be either empty or another, simpler inductive case of $w$, but I have trouble writing out this proof formally.
Suppose without loss of generality that $w$ starts with a $0$. Then, count along the letters in $w$, and keep track of the number of zeroes you have seen minus the number of ones you have seen. So if $w = 000110111100$, then your counting goes $1, 2, 3, 2, 1, 2, 1, 0, -1, -2, -1, 0$. Clearly in the end you must have gotten to 0, since there are an equal number of zeroes and ones. This means that at some point you must drop to zero, that is, at some point you must count $1, 0$. You can see this in our example above.
When you get to that 1, you have counted a substring which has the initial 0, and then after that an equal number of zeroes and ones; and because you then drop to 0, there must be another 1 after that substring. Thus we collect the substring to get $x$, and we write $w = 0x1y$, where $y$ is whatever is left. In our example, we get $w = 0(001101)1(1100)$.
The first character of the string has to be a $0$ or a $1$. Since the number of $0$'s is equal to the number of $1$'s, if the first character is $0$, there has to be a $1$ further ahead and if the first character is $1$, there has to be a $0$ further ahead.
