Quantas palavras binárias de comprimento 10 começam ou terminam com 1?
Passo 1
Vou deixar claro o que o enunciado pede e os dados que temos:
- Pergunta: quantas palavras binárias de comprimento
começam ou terminam com (ou seja, começam com , ou terminam com , ou fazem as duas coisas)? - Informação dada: "palavra binária de comprimento
" significa uma sequência de bits onde cada bit pode ser ou .
Isso é tudo que precisamos identificar antes de começar a contar.
Passo 2
Ideia geral de contagem (a ferramenta que vamos usar): contar conjuntos usando o princípio da adição com correção para interseção (princípio da inclusão-exclusão). Também é útil lembrar que, se em uma palavra binária alguns bits são fixos, os bits restantes são livres e cada bit livre tem
escolhas, então se há
bits livres existem
palavras possíveis. Vou aplicar essas ideias passo a passo.
Passo 3
Defino dois conjuntos para organizar o problema:
- Seja
o conjunto das palavras binárias de comprimento que começam com . - Seja
o conjunto das palavras binárias de comprimento que terminam com .
Quero calcular
, o número de palavras que começam ou terminam com
.
Passo 4
Conto
: se a palavra começa com
, o primeiro bit está fixo como
e restam
bits livres. Cada bit livre tem
escolhas, então
Calculo o valor numérico:
.
Passo 5
Conto
: de modo análogo, se a palavra termina com
o último bit está fixo e restam
bits livres, então
Passo 6
Conto a interseção
: são as palavras que começam E terminam com
. Isso fixa o primeiro e o último bit (dois bits fixos), sobrando
bits livres. Logo
E numericamente
.
Passo 7
Aplico a fórmula da inclusão-exclusão para obter
:
Substituindo os valores:
Uma maneira alternativa (checagem rápida): contar o complementar — palavras que NÃO começam nem terminam com
têm primeiro e último bit iguais a
, restando
bits livres, ou seja
dessas; como há
palavras no total, o número desejado é
, concordando com o cálculo anterior.
Passo 8
Resumo final rápido e um empurrãozinho de ânimo: a resposta é
. Se quiser, a gente pode praticar variações (por exemplo: começam com dois
s ou terminam com dois
s) para fixar o método — tu tá indo bem, calma que dá tempo de aprender isso direito!