cr001 ha dado un enfoque. Otra idea es aplastar cada subcadena de bits idénticos a un solo bit, de modo que, por ejemplo $0010111001$ se reduce a $010101$ . El resultado es siempre una cadena que alterna ceros y unos y tiene el mismo número de $01$ pares y el mismo número de $10$ como la cadena original. Es muy fácil comprobar que si la cadena de bits es alterna, el número de $01$ y el número de $10$ pueden diferir como máximo en $1$ . Tal como está, este argumento es un poco informal, aunque ciertamente contiene todas las ideas esenciales. Esbozaré una forma de hacerlo más formal.
Supongamos que su cadena de bits $\mathbf{b}$ es $b_1b_2\ldots b_n$ . Sea
$$D=\{k\in[n]:k=1\text{ or }b_k\ne b_{k-1}\}\;.$$
Supongamos que $D=\{k_1,\ldots,k_m\}$ , donde $k_1<\ldots<k_m$ .
- Demuestre que si $k_i\le\ell<k_{i+1}$ entonces $b_\ell=b_k$ .
- Demuestre que la cadena de bits $b_{k_1}b_{k_2}\ldots b_{k_m}$ alterna ceros y unos: no contiene una subcadena $00$ o $11$ .
- Demuestre que la cadena de bits $b_{k_1}b_{k_2}\ldots b_{k_m}$ tiene el mismo número de $01$ subcadenas y el mismo número de $10$ subcadenas como $\mathbf{b}$ .
- Concluir que el número de $01$ subcadenas de $\mathbf{b}$ y el número de $10$ subcadenas de $\mathbf{b}$ difieren como máximo en $1$ .
Reducir $\mathbf{b}$ a $b_{k_1}b_{k_2}\ldots b_{k_m}$ es simplemente aplastar cada subcadena de bits idénticos hasta un solo bit, el primero de la subcadena.
Para divertirse, he aquí una forma más elegante de hacer lo mismo, utilizando una idea que resulta fructífera en un número sorprendente de entornos. Definir una relación $\sim$ en $[n]=\{1,2,\ldots,n\}$ como sigue: para $k,\ell\in[n]$ , $k\sim\ell$ si y sólo si
- $k\le\ell$ y $b_i=b_k$ para todos $i$ tal que $k\le i\le\ell$ o
- $\ell<k$ y $b_i=b_k$ para todos $i$ tal que $\ell\le i\le k$ .
En otras palabras, $k\sim\ell$ si y sólo si $b_k$ , $b_\ell$ y los bits entre ellos son todos iguales.
- Demostrar que $\sim$ es una relación de equivalencia en $[n]$ .
Para $k\in[n]$ dejar $\bar k$ sea el $\sim$ -clase de equivalencia de $k$ .
- Demuestre que si $\bar k$ y $\bar\ell$ son clases de equivalencia distintas, entonces $k<\ell$ si y sólo si $i<j$ siempre que $i\in\bar k$ y $j\in\bar\ell$ .
Supongamos que hay $m$ clases de equivalencia, digamos $\bar{k}_1,\bar{k}_2,\ldots,\bar{k}_m$ donde podemos suponer que $k_1<k_2<\ldots<k_m$ .
- Demuestre que la cadena de bits $b_{k_1}b_{k_2}\ldots b_{k_m}$ alterna ceros y unos: no contiene una subcadena $00$ o $11$ .
- Demuestre que la cadena de bits $b_{k_1}b_{k_2}\ldots b_{k_m}$ tiene el mismo número de $01$ subcadenas y el mismo número de $10$ subcadenas como $\mathbf{b}$ .
- Concluir que el número de $01$ subcadenas de $\mathbf{b}$ y el número de $10$ subcadenas de $\mathbf{b}$ difieren como máximo en $1$ .
En esta versión, cada clase de equivalencia es una subcadena máxima de bits idénticos.
