0

I have $R$ represents a set of binary strings. also $y \times z$ represents the concatenation of strings $y$ and $z$. So if $y = 010$ and $z = 001$ then $y \times z = 010001$. I need to prove that for any string in $R$ of length $\geq 0$ in the form $p = y \times z$, I can express $y$ and $z$ such that the number of 0's in $y$ is the same as the number of 1's in $z$

For Base case $n=0$ its trivially true as both $y$ and $z$ are empty and have $0$ $0$'s and $0$ $1$'s.

From there I was thinking of assuming it applies for $n = k+1$ and showing that it would then work for $n =k$ as a result.

Not sure if this is the correct logic or if I'm doing something wrong.

Hopper
  • 139

2 Answers2

3

It seems that this can be shown in a straightforward manner.

Suppose you start by splitting such that $y$ is empty, and $z=R$. Let $y_0$ track the number of $0$'s in $y$ (currently $0$) and $z_1$ the number of 1's in $z$ (starts at some number $I\geq 0$).

Now repeatedly shift the division one to the right. If the currently leftmost digit in $z$ is a 0, $y_0$ increases by 1; else it's a 1, and $z_1$ decreases by one. Either way, $z_1 - y_0$ is initially $I$ and decreases by 1 each step; eventually (namely, after exactly $I$ steps) it must reach 0, which is the desired split.

DavidP
  • 24
2

It might work out for you, but I am thinking of a non-inductive strategy that would probably be easier.

Let a string $X$ with length $n$ be given. For a positive integer $i$, let $a(i)$ represent the number of 0's in the first $i$ digits of $X$, and let $b(i)$ represent the number of 1's in the last $n-i$ digits of $X$. You need to show that there is some $i$ such that $a(i)=b(i)$.

HINT: A man climbed a mountain one morning starting at 9:00 AM and started climbing down the next morning at 9:00AM. Show that there must be some time of the day when he was at the exact same altitude at the exact same time on the two days. (Your problem is different in that it is discrete rather than continuous, but you can work around that.)

  • Don't really understand. If we have a string of length $n$ and we start with $a(i) = 0$ and end at $a(i) = k$ then we know that we must start $b(i) = n - k$ and end with $b(i) = 0$. Not sure how to proceed from there since the two end points and start points aren't all the same. – Hopper Oct 06 '19 at 21:55