© O código morse usa "palavras"contendo de 1 a 4 “letras”, sendo elas ponto e traço. Quantas "palavras"existem no código morse?
Passo 1
O enunciado dá as seguintes informações e pede uma única contagem:
- As “letras” do código Morse, para este problema, são apenas dois símbolos: ponto e traço. Ou seja, o alfabeto tem exatamente
símbolos. - Uma “palavra” do código Morse pode ter comprimento
, , ou (ou seja, comprimentos entre e inclusive).
O que se pede: contar quantas “palavras” diferentes existem com essas regras (ou seja, todas as sequências possíveis de comprimentoa formadas por ponto/traço).
Passo 2
Princípio básico de contagem (regra do produto): se uma sequência tem
posições e em cada posição há
escolhas independentes, então o número total de sequências é
. Aqui, cada posição pode ser ponto ou traço, logo
. Para um comprimento fixo
temos, portanto,
sequências possíveis. Explicando com calma: para a primeira posição existem
escolhas; para cada escolha da primeira, para a segunda posição existem
escolhas novamente; multiplicando dá
para comprimento
, e assim por diante.
Passo 3
Aplicando isso para cada comprimento permitido:
- Para comprimento
há palavras. - Para comprimento
há palavras. - Para comprimento
há palavras. - Para comprimento
há palavras.
Podemos até exemplificar mentalmente: paraas sequências são todas as possíveis combinações de três símbolos, por exemplo (ponto/ponto/ponto), (ponto/ponto/traço), …, (traço/traço/traço).
Passo 4
Agora somamos todas as palavras de todos os comprimentos permitidos:
Somando passo a passo:
Passo 5
Forma geral (fórmula de soma geométrica) — uma maneira rápida e elegante: para
,
Aqui
e
, logo
Outra forma equivalente é usar
e subtrair o termo
(que é
), obtendo
.
Passo 6
Verificação rápida por intuição: o número
faz sentido porque o conjunto de todas as sequências de até
bits (0/1) sem a sequência vazia tem tamanho
; é uma quantidade pequena e fácil de conferir com listagem curta se necessário. Está tudo coerente.