Como é possível encontrar o número da cadeia de bits de extensão 10 que ou começa com 101 ou termina com 010 ?

Passo 1

O enunciado pede o número de cadeias binárias de extensão \,10 que ou começam com \,101 ou terminam com \,010.
Conteúdo da matéria: princípio fundamental da contagem e princípio de inclusão-exclusão.

Passo 2

Definimos A como o conjunto de cadeias que começam com \,101. Nesse caso, os 3 primeiros bits estão fixos e os 7 bits restantes podem ser 0 ou 1 livremente. Pelo princípio da multiplicação,
|A| = 2^7.

Passo 3

Definimos B como o conjunto de cadeias que terminam com \,010. Analogamente, os 3 últimos bits estão fixos e os outros 7 livres, de modo que
|B| = 2^7.

Passo 4

Para A\cap B, queremos cadeias que simultaneamente comecem com \,101 e terminem com \,010. Há 3 bits fixos no início e 3 no fim, restando 10 - 6 = 4 bits livres. Assim,
|A\cap B| = 2^4.

Passo 5

Aplicando o princípio de inclusão-exclusão para obter A\cup B,
|A \cup B| = |A| + |B| - |A\cap B| = 2^7 + 2^7 - 2^4 = 128 + 128 - 16 = 240.

Resposta

O número de cadeias de extensão \,10 que ou começam com \,101 ou terminam com \,010 é 240.

Exercícios de Livros Relacionados