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 1,2,3,4,5, 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 n evitam o bloco proibido.

Passo 2

Defina an como o número de sequências de comprimento n sobre o alfabeto 1,2,3,4,5 que não contêm “13”.
Para montar uma sequência de tamanho n, considere o último dígito:
  • Se for 1, não cria “13” ao concatenar após qualquer sequência de tamanho n-1 que já evita “13”. Logo há an-1 maneiras.
  • Se for din2,4,5, também não cria “13” independentemente do que vinha antes, dando mais 3,an-1.
  • Se for 3, não se pode ter tido “1” imediatamente antes, então vêm apenas das sequências de tamanho n-1 que terminam em algo diferente de 1; o número dessas é an-1-bn-1, mas veremos que isso gera a recorrência simples
Combinando tudo obtém-se
an ;=; an-1 ;+;3,an-1;+;(an-1-bn-1)
e usando bn-1=an-2 (número de sequências terminando em 1 de comprimento n-1) resulta
an ;=;5,an-1-an-2

Passo 3

Precisamos de condições iniciais:
;;a0=1 (sequência vazia)
;;a1=5 (qualquer dígito)
Para n=2, há 5^2=25 pares no total, mas excluímos o único par “13”, ficando
a2 =25-1=24

Passo 4

Agora aplicamos a recorrência
a3 =5,a2 - a1 =5cdot24 -5 =120 -5 =115,
a4 =5,a3 - a2 =5cdot115 -24 =575 -24 =551

Resposta

551 maneiras distintas.

Exercícios relacionados