Explique como encontrar o número de cadeias de bits de extensão não excedente a 10 que tenham pelo menos um bit 0 .

Passo 1

O problema pede o número de cadeias de bits cuja extensão (comprimento) é no máximo 10 e que contenham pelo menos um bit 0.
Conteúdo utilizado: contagem de cadeias binárias, soma de progressão geométrica e princípio do complemento.

Passo 2

Primeiro, vamos contar todas as cadeias de bits de extensão não excedente a 10. Para cada k de 0 a 10, há 2^k cadeias de comprimento k. Logo o total é
\sum_{k=0}^{10} 2^k \;=\;\frac{2^{11}-1}{2-1}\;=\;2^{11}-1\;=\;2047.

Passo 3

Agora, contamos quantas dessas cadeias não têm nenhum bit 0, ou seja, são formadas só por 1’s.
Para cada k de 0 a 10 existe exatamente uma cadeia “toda 1’s” (inclusive a cadeia vazia, k=0). Então há 11 cadeias sem nenhum 0.

Passo 4

Pelo princípio do complemento, o número de cadeias que têm pelo menos um 0 é
(\text{total de cadeias}) - (\text{cadeias sem 0}) = (2^{11}-1) - 11 = 2047 - 11 = 2036.

Resposta

2036
Número de cadeias de bits de extensão não excedente a 10 que têm pelo menos um bit 0.

Exercícios de Livros Relacionados