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.
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
de 0 a 10, há
cadeias de comprimento
. Logo o total é
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 de 0 a 10 existe exatamente uma cadeia “toda 1’s” (inclusive a cadeia vazia,
). Então há
cadeias sem nenhum 0.
Para cada
Passo 4
Pelo princípio do complemento, o número de cadeias que têm pelo menos um 0 é
Resposta
Número de cadeias de bits de extensão não excedente a 10 que têm pelo menos um bit 0.