Jtdylktuy

The full question is as follows.

Prove that every binary string of length $n$ can be split down into 2 substrings where string $S = A.B$ such that the number of $0's$ in A is equal to the number of $1's$ in B.

Example:

a) String $010010$ can be split as $01.0010$. The number of $0's$ in A is $1$ and the number of $1's$ in B is $1$ too.

b) String $11101000$ can be split as $1110.1000$

I am stumped, I don't know how to apply any of the classic proof techniques I usually use.

Let the state of a split be $(a,b)$ where $a$ is the number of zeros on the left and $b$ the number of ones on the right.

Start by considering the split of a string of length $n$ with $A=epsilon$ (the empty string), in state $(0,k)$ and consider advancing one letter.

Suppose you are in state $(a,b),$ and you advance over a 0. Now you are in state $(a+1,b).$ If you advance over a 1 you are in state $(a,b-1).$

You start in state $(0,k)$ and end in state $(n-k,0)$ and only advance by 1 in one coordinate so you must end up with a state where both sides are equal.

If you correspond states with points in space, then you start above or on the line $y=x$, can only move one unit at a time, down or right as you advance through the string, and end below or on the line. You must hit the line in between.

Proceed by induction.

1. Base step: the empty string can be trivially divided.
   
   (Or, $0$ can be split as $.0$, and $1$ as $1.$ having no $0$'s on the left side and no $1$'s on the right side.)


2. Suppose that all binary strings of length $le n$ can be so divided, and let $w=(w_0,dots,w_n)$ be a string of length $n+1$.
   
   If $w_0=1$, we can use the same splitting as for $(w_1,dots,w_n)$.
   
   Similarly, if $w_n=0$, we can use the same splitting as for $(w_0,dots,w_{n-1})$.
   
   Finally, if $w_0=0$ and $w_n=1$, we can use the same splitting as for $(w_1,dots,w_{n-1})$, as now both the count of $0$'s in $A$ and the count of $1$'s in $B$ are increased by one.

A simpler argument:

The string can be split at the location where the length of A equals the number of 1s in S, and the length of B equals the number of 0s in S.

Let the number of 0s in S be $0_S$, the number of 0s in A be $0_A$, and the number of 0s in B be $0_B$, and define $1_S$, $1_A$ and $1_B$ similarly.

We know that $|A| = 0_A + 1_A$, but also $|A| = 1_S = 1_A + 1_B$

Therefore, $0_A + 1_A = 1_A + 1_B$, which implies that $0_A = 1_B$, as desired.

This can be proved with induction on $n$.

Let $0_S$ denotes the number of $0$'s in string $S$ and let $1_S$ denote the number of $1$'s in string $S$.

By induction $S$ can be split as $U.V.0$ or $U.V.1$ such that $0_U=1_V$

If $S=U.V.0$ then for $A=U$ and $B=V.0$ we find $0_A=0_U=1_V=1_V+0=1_B$

If $S=U.V.1$ and $W$ denotes the first character of $V.1$ so that $V=WR$ then we can take $A=UW$ and $B=R.1$.

This because:

if $W=0$ then $0_A=0_U+1=1_V+1=1_R+1=1_B$

if $W=1$ then $0_A=0_U+0_W=1_V=1_R+1=1_B$

Applying this backwards on the strings $010010$ and $11101000$ mentioned in your question we get:

• $|$


• $|0$


• $0|1$


• $0|10$


• $0|100$


• $01|001$


• $01|0010$

and:

• $|$


• $1|$


• $11|$


• $111|$


• $111|0$


• $1110|1$


• $1110|10$


• $1110|100$


• $1110|1000$

Observe that there is shift to the right if a $1$ is added and there is no shift if a $0$ is added.

Step 1: Put your left index finger to the left of the string and your right index finger to the right.

Step 2: Move your left index finger to the leftmost 0, and your right index finger to the rightmost 1. Then, as long as you can do so without your fingers crossing, move your left index finger to the next leftmost 0, and your right index finger to the next rightmost 1.

Step3: As long as there is a 1 to the right of your left index finger, move your left index finger to the right, and as long as there is a 0 to the left of your right index finger, move your right index finger to the left.

Example:

Step 1: $010010$

Step 2: $underline0100underline10$

Step 3a: $0underline10underline010$

Step 3b:$0underline1underline0010$

At the end of step 2, you can't have a 0 followed by a 1 between your fingers, because if you did, you could move your fingers together more. At the end of step 3, your fingers have to be together; if there were a 1 to the right of your left index finger, you would have moved it to the right, if there were a 0 to the left of your right index finger, you would have moved it to the left, and if there were a 0 next to your left index finger and a 1 next to your right index finger, then there would be a 0 followed by a 1.

Since your fingers counted out equal numbers of 0s and 1s, respectively, in Step 2, and your left index finger didn't increase in number of 0s, nor your right index finger in 1s, in Step 3, it follows that your fingers define a split that has equal numbers.