Exercício 1.2.16. Maria deve criar uma senha de 4 dígitos para sua conta bancária. Nessa senha, somente os algarismos 1,2,3,4,5 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 a quantidade de sequências de comprimento 4 cujos termos são escolhidos em
, admitindo repetição, de modo que não apareça nunca o bloco “13” (isto é, o dígito 1 seguido imediatamente de 3).
Conteúdo: contagem de sequências restringidas (combinatória de cadeias). Vamos usar uma recorrência para contar quantas sequências de tamanho evitam o bloco proibido.
Conteúdo: contagem de sequências restringidas (combinatória de cadeias). Vamos usar uma recorrência para contar quantas sequências de tamanho
Passo 2
Defina
como o número de sequências de comprimento
sobre o alfabeto
que não contêm “13”.
Para montar uma sequência de tamanho , considere o último dígito:
Para montar uma sequência de tamanho
- Se for
, não cria “13” ao concatenar após qualquer sequência de tamanho que já evita “13”. Logo há maneiras. - Se for
, também não cria “13” independentemente do que vinha antes, dando mais . - Se for
, não se pode ter tido “1” imediatamente antes, então vêm apenas das sequências de tamanho que terminam em algo diferente de 1; o número dessas é , mas veremos que isso gera a recorrência simples
Combinando tudo obtém-se
e usando
(número de sequências terminando em 1 de comprimento
) resulta
Passo 3
Precisamos de condições iniciais:
(sequência vazia)
(qualquer dígito)
Para , há
pares no total, mas excluímos o único par “13”, ficando
Para
Passo 4
Agora aplicamos a recorrência
Resposta
551 maneiras distintas.