Maria deve criar uma senha de 4 dígitos para sua conta bancária. Nessa senha, somente os algarismos
podem ser usados e um mesmo algarismo pode aparecer mais de uma vez. Contudo, supersticiosa, Maria não quer que sua senha contenha o número 13 , isto é, o algarismo 1 seguido imediatamente pelo algarismo 3. De quantas maneiras distintas Maria pode escolher sua senha?
Passo 1
O enunciado pede: contar de quantas maneiras Maria pode escolher uma senha de 4 dígitos sujeita a estas condições:
- Apenas os algarismos
podem ser usados. - Um mesmo algarismo pode repetir-se quantas vezes quiser.
- A senha não pode conter a sequência
(isto é, o algarismo imediatamente seguido pelo algarismo ) em nenhuma posição.
Informações relevantes obtidas do enunciado:
- Comprimento da senha:
dígitos. - Alfabeto disponível:
(tamanho ). - Proibição: a substring
não pode aparecer em posições , ou .
Passo 2
Primeiro conte quantas senhas existem sem nenhuma restrição (apenas para ter a base de comparação).
Cada posição tem opções independentemente, e são
posições, logo o total sem restrição é
Cada posição tem
Expliquei por que: quando escolhas são independentes e cada uma tem
opções, o número total de sequências de comprimento
é
. Aqui
e
.
Passo 3
Agora vamos contar quantas senhas são proibidas, ou seja, que contêm a substring
pelo menos uma vez. Depois subtraímos desse total para obter as senhas permitidas.
Uma maneira direta e segura para isso é usar o princípio da inclusão-exclusão: contamos quantas senhas têm na posição
, quantas na posição
, quantas na posição
, somamos, subtraímos as interseções duplas (senhas que têm
em duas posições diferentes), e somamos a interseção tripla se houver.
Uma maneira direta e segura para isso é usar o princípio da inclusão-exclusão: contamos quantas senhas têm
Passo 4
Defina os eventos:
-
= conjunto de senhas com em . -
= conjunto de senhas com em . -
= conjunto de senhas com em .
Calcule
: fixando posições
e
como
e
respectivamente, as posições
e
são livres, cada uma com
opções, então
O mesmo raciocínio vale para
e
, pois em cada caso fixamos duas posições consecutivas e as outras duas ficam livres. Assim
Observação didática: aqui usei a regra do produto novamente — após fixar alguns dígitos, as posições restantes independentes geram multiplicação das opções.
Passo 5
Agora as interseções duplas:
-
: isso exigiria que as posições fossem simultaneamente (para ) e (para em ). Para que ocorra precisamos de posição e posição ; já pede posição . Isso dá um conflito (posição teria de ser e ao mesmo tempo), logo
- Pela mesma razão,
também é impossível (conflito na posição ), logo
-
: aqui as ocorrências são em posições disjuntas e . Para isso precisamos que a senha seja exatamente , ou seja há exatamente sequência que satisfaz ambas. Portanto
Passo 6
Aplicando o princípio da inclusão-exclusão para contar quantas senhas têm pelo menos uma ocorrência de
:
Substituindo os valores encontrados:
Expliquei cada termo: somamos os casos simples, subtraímos interseções duplas que foram contadas duas vezes, e adicionamos a interseção tripla se existisse (aqui é zero).
Passo 7
Calculamos explicitamente o número de senhas proibidas (a expressão do passo anterior simplificada):
Isso nos dá o total de senhas que contêm a substring
pelo menos uma vez.
Passo 8
Finalmente, o número de senhas permitidas (sem a substring
) é o total sem restrição menos as proibidas. Escrevemos isso symbolicamente para não repetir a resposta final fora da seção de resposta:
Breve comentário pedagógico: a ideia é sempre tentar contar o total e eliminar as configurações proibidas, mas atenção às interseções quando a proibição pode ocorrer em várias posições — por isso a inclusão-exclusão é útil. Se preferir um método alternativo, dá para modelar isso por um pequeno autômato/recorrência que conta sequências sem atingir a substring proibida; esse método leva ao mesmo resultado.