Quantas palavras binárias de comprimento menor ou igual a 6 existem?
Passo 1
O enunciado pede: “Quantas palavras binárias de comprimento menor ou igual a 6 existem?”
Informações dadas/assumidas claramente a partir do enunciado:
Informações dadas/assumidas claramente a partir do enunciado:
- Alfabeto binário: as palavras são formadas pelos símbolos
e . - “Comprimento” significa o número de símbolos (bits) na palavra.
- Os comprimentos possíveis são
(inclui a palavra vazia de comprimento ).
Passo 2
Contar palavras de um comprimento fixo
.
Se uma palavra tem exatamente posições (ou seja, comprimento
), cada posição pode ser preenchida com
ou
. São
escolhas para cada posição, e as escolhas são independentes entre posições. Pelo princípio multiplicativo (produto de opções por posição), o número de palavras de comprimento
é
Se uma palavra tem exatamente
Exemplos pequenos para fixar a intuição:
- Para
(palavra vazia) há exatamente palavra. - Para
há palavras: e . - Para
há palavras: .
Passo 3
Contar palavras de comprimento menor ou igual a
.
Somando as quantidades para cada comprimento obtemos
Somando as quantidades para cada comprimento
Essa soma é uma soma geométrica finita. Vamos usar a fórmula geral da soma geométrica: para
e inteiro
,
Breve demonstração da fórmula (muito útil na prova): seja
. Multiplicando por
dá
. Subtraindo
de
cancela quase todos os termos, ficando
. Fatorando,
, daí
.
Passo 4
Aplicar a fórmula com
e
. Assim
Calcule
:
. Portanto
Verificação direta (opcional):
.
Passo 5
Interpretação final: existem
palavras binárias cujo comprimento é menor ou igual a
, contando a palavra vazia. Se, por acaso, o enunciado não quisesse contar a palavra vazia, bastaria subtrair
e obter
; mas a interpretação adotada aqui inclui o comprimento
.