¿Cuántas cadenas de bits de longitud 8 comienzan con "1" o terminan con "01"?

Question

Una cadena de bits es una secuencia finita de los números $ 0 $ y $ 1 $. Supongamos que tenemos una cadena de bits de longitud $ 8 $ que comienza con un $ 1 $ o termina con un $ 01 $, ¿cuántas cadenas de bits totales posibles tenemos?

Estoy pensando que para las cadenas que comienzan con un 1, tendríamos $ 8 - 1 = 7 $ bits para elegir, ¿así que $ 2^7 $ cadenas de bits posibles de longitud $ 8 $ que comienzan con un $ 1 $?

¿Puedo abordar la segunda condición de la misma manera y simplemente sumar los totales? Es decir, ¿si mi lógica es correcta en primer lugar?

Answer 1

Interpretamos que comienza con $1$ o termina en $01$ significa que las cadenas de bits que satisfacen ambas condiciones califican.

Según tu análisis correcto, hay $2^7$ cadenas de bits que comienzan con $1$.

De manera similar, hay $2^6$ cadenas de bits que terminan con $01$.

La suma $2^7+2^6$ doblemente cuenta las cadenas de bits que comienzan con $1$ y terminan con $01$.

Hay $2^5$ de estas, por lo que hay $2^7+2^6-2^5$ cadenas de bits que comienzan con $1$ o terminan con $01$.

Answer 2

La estrategia que pareces estar proponiendo es tener en cuenta que hay $2^7$ cadenas de bits que comienzan con $1$ y $2^6$ que terminan con $01$, ya que se pueden hacer $7$ elecciones en el primer caso y $6$ elecciones en el segundo. Si sumáramos estos para obtener $2^6+2^7$, esto no funciona del todo para contar el número de cadenas que satisfacen alguna de las condiciones. En particular, considera una cadena como $$10000001$$ ya que tanto comienza con $1$ como termina con $01$, por lo que el método anterior la habría contado dos veces. La solución para esto es restar el número de cadenas que cumplen ambas condiciones de la suma $2^6+2^7 para compensar por contar esas cadenas dos veces.

Esto es el principio de inclusión-exclusión.

Answer 3

Aquí hay otra forma de llegar a la respuesta, sin hacer todo el "recuento doble y luego corregirlo" baile:

De todos los octetos posibles (cadenas de 8 bits), la mitad de ellos comenzará con $1$. De la otra mitad (es decir, aquellos que empiezan con $0$), un cuarto terminará con $01$. Dado que hay $2^8$ octetos posibles, tenemos: $$ 2^8 \times \frac{1}{2} + 2^8 \times \frac{1}{2} \times \frac{1}{4} \\ 2^7 + 2^5 $$ Si bien esto puede no verse idéntico a las otras respuestas, nota que: $$ 2^5 = 2^6 - 2^5 $$ porque $$ 2^6 - 2^5 = 2 \times 2^5 - 2^5 = 2^5 + 2^5 - 2^5 = 2^5 $$

Answer 4

Aunque las otras respuestas te muestran cómo trabajar tu lógica en una aplicación correcta del principio de inclusión-exclusión, uno podría tomar un enfoque ligeramente diferente y sumar tamaños de conjuntos de eventos no intersecantes.

Caso 1:

El primer dígito binario es 1. Dada esta condición, todas las cadenas posibles con el atributo cumplen la condición requerida 'O'. Así que hay $2^7$ cadenas en este conjunto.

Caso 2:

El primer dígito binario es 0. Dada esta condición, solo las cadenas que terminan en $01$ cumplen la condición requerida. Esto deja solo 5 dígitos binarios para elegir libremente: contamos todas de la forma $0xxxxx01$. Así que hay $2^5$ cadenas en este conjunto.

Sumando el número de combinaciones para las dos condiciones mutuamente excluyentes, pero exhaustivas, obtenemos $2^7 + 2^5$ combinaciones.