Dividir una cadena en 2 partes de forma que el número de 1's de la parte A sea igual al número de 0's de la parte B.

Question

La pregunta completa es la siguiente.

Demostrar que toda cadena binaria de longitud $n$ puede dividirse en 2 subcadenas donde la cadena $S = A.B$ tal que el número de $0's$ en A es igual al número de $1's$ en B.

Ejemplo:

a) Cadena $010010$ se puede dividir como $01.0010$ . El número de $0's$ en A es $1$ y el número de $1's$ en B es $1$ también.

b) Cadena $11101000$ se puede dividir como $1110.1000$

Estoy perplejo, no sé cómo aplicar ninguna de las técnicas de prueba clásicas que suelo utilizar.

Answer 1

Que el estado de una división sea $(a,b)$ donde $a$ es el número de ceros a la izquierda y $b$ el número de los de la derecha.

Comience por considerar la división de una cadena de longitud $n$ con $A=\epsilon$ (la cadena vacía), en el estado $(0,k)$ y considerar el avance de una letra.

Suponga que está en el estado $(a,b),$ y avanzas sobre un 0. Ahora estás en el estado $(a+1,b).$ Si avanza sobre un 1 está en estado $(a,b-1).$

Comienza en el estado $(0,k)$ y terminan en el estado $(n-k,0)$ y sólo avanza en 1 en una coordenada, por lo que debe terminar con un estado en el que ambos lados sean iguales.

Si los estados se corresponden con puntos en el espacio, entonces se empieza por encima o en la línea $y=x$ , sólo puede moverse una unidad a la vez, hacia abajo o hacia la derecha a medida que avanza por la cadena, y terminar por debajo o sobre la línea. Debes golpear la línea en el medio.

Answer 2

Proceda por inducción.

1. Paso básico: la cadena vacía se puede dividir trivialmente.
   (O, $0$ se puede dividir como $.0$ y $1$ como $1.$ sin tener $0$ en el lado izquierdo y ningún $1$ en el lado derecho).
2. Supongamos que todas las cadenas binarias de longitud $\le n$ puede estar tan dividido, y que $w=(w_0,\dots,w_n)$ sea una cadena de longitud $n+1$ .
   Si $w_0=1$ podemos utilizar la misma división que para $(w_1,\dots,w_n)$ .
   Del mismo modo, si $w_n=0$ podemos utilizar la misma división que para $(w_0,\dots,w_{n-1})$ .
   Por último, si $w_0=0$ y $w_n=1$ podemos utilizar la misma división que para $(w_1,\dots,w_{n-1})$ ya que ahora tanto el recuento de $0$ 's en $A$ y el recuento de $1$ 's en $B$ se incrementan en uno.

Answer 3

Un argumento más sencillo:

La cadena se puede dividir en el lugar donde la longitud de A es igual al número de 1s en S, y la longitud de B es igual al número de 0s en S.

Sea el número de 0s en S $0_S$ el número de 0s en A sea $0_A$ y el número de 0s en B sea $0_B$ y definir $1_S$ , $1_A$ y $1_B$ de manera similar.

Sabemos que $|A| = 0_A + 1_A$ pero también $|A| = 1_S = 1_A + 1_B$

Por lo tanto, $0_A + 1_A = 1_A + 1_B$ lo que implica que $0_A = 1_B$ , según se desee.

Answer 4

Esto se puede demostrar con la inducción en $n$ .

Dejemos que $0_S$ denota el número de $0$ 's en la cadena $S$ y que $1_S$ denotan el número de $1$ 's en la cadena $S$ .

---

Por inducción $S$ se puede dividir como $U.V.0$ o $U.V.1$ tal que $0_U=1_V$

Si $S=U.V.0$ entonces para $A=U$ y $B=V.0$ encontramos $0_A=0_U=1_V=1_V+0=1_B$

Si $S=U.V.1$ y $W$ denota el primer carácter de $V.1$ para que $V=WR$ entonces podemos tomar $A=UW$ y $B=R.1$ .

Esto porque:

si $W=0$ entonces $0_A=0_U+1=1_V+1=1_R+1=1_B$

si $W=1$ entonces $0_A=0_U+0_W=1_V=1_R+1=1_B$

---

Aplicando esto al revés en las cuerdas $010010$ y $11101000$ mencionado en su pregunta obtenemos:

• $|$
• $|0$
• $0|1$
• $0|10$
• $0|100$
• $01|001$
• $01|0010$

y:

• $|$
• $1|$
• $11|$
• $111|$
• $111|0$
• $1110|1$
• $1110|10$
• $1110|100$
• $1110|1000$

Obsérvese que hay un desplazamiento hacia la derecha si a $1$ se añade y no hay desplazamiento si un $0$ se añade.

Answer 5

Paso 1: Coloca el dedo índice izquierdo a la izquierda de la cuerda y el derecho a la derecha.

Paso 2: Mueve tu dedo índice izquierdo al 0 más a la izquierda, y tu dedo índice derecho al 1 más a la derecha. Luego, siempre que puedas hacerlo sin que se crucen tus dedos, mueve tu dedo índice izquierdo al siguiente 0 más a la izquierda, y tu dedo índice derecho al siguiente 1 más a la derecha.

Paso3: Mientras haya un 1 a la derecha de tu dedo índice izquierdo, mueve tu dedo índice izquierdo hacia la derecha, y mientras haya un 0 a la izquierda de tu dedo índice derecho, mueve tu dedo índice derecho hacia la izquierda.

Ejemplo:

Paso 1: $010010$
Paso 2: $\underline0100\underline10$
Paso 3a: $0\underline10\underline010$
Paso 3b: $0\underline1\underline0010$

Al final del paso 2, no puedes tener un 0 seguido de un 1 entre los dedos, porque si lo hicieras, podrías mover los dedos más juntos. Al final del paso 3, tus dedos tienen que estar juntos; si hubiera un 1 a la derecha de tu dedo índice izquierdo, lo habrías movido hacia la derecha, si hubiera un 0 a la izquierda de tu dedo índice derecho, lo habrías movido hacia la izquierda, y si hubiera un 0 junto a tu dedo índice izquierdo y un 1 junto a tu dedo índice derecho, entonces habría un 0 seguido de un 1.

Como tus dedos contaron números iguales de 0s y 1s, respectivamente, en el paso 2, y tu dedo índice izquierdo no aumentó en número de 0s, ni tu dedo índice derecho en 1s, en el paso 3, se deduce que tus dedos definen una división que tiene números iguales.