(Fuvest-SP) 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?
a) 551
b) 552
c) 553
d) 554
e) 555

Passo 1

Resumindo: queremos formar senhas de 4 dígitos usando os algarismos 1,2,3,4,5 com repetição permitida, mas proibindo o padrão “13” (isto é, o dígito 1 não pode ser seguido imediatamente de 3). O conteúdo é contagem de sequências com restrição de subcadeia, e usaremos um método de recorrência via estados.

Passo 2

Definimos dois estados para sequências de comprimento n que não contêm “13”:
A(n): número de sequências de comprimento n que terminam em 1.
B(n): número de sequências de comprimento n que terminam em algum dígito de 2,3,4,5.
O total sem “13” é an = A(n) + B(n).

Passo 3

Para estender uma sequência válida de tamanho n a n+1:
  • Se quisermos terminar em 1, podemos anexar 1 a qualquer sequência de tamanho n. Logo,
A(n+1) = A(n) + B(n) = an
  • Se quisermos terminar em 2,3,4,5, devemos evitar anexar 3 após uma sequência que já termina em 1. Há 3 escolhas 2,4,5 possíveis após qualquer estado, e 1 escolha (o dígito 3) apenas após um estado que termina em não-1. Assim,
B(n+1) = 3,A(n) + 4,B(n)

Passo 4

Inicialmente, para n=1:
A(1)=1(só a sequência 1), B(1)=4(2,3,4 ou 5) óê
Logo a1=5. Agora iteramos:
Para n=2:
A(2)=a1=5, B(2)=3cdot A(1)+4cdot B(1)=3cdot1+4cdot4=19, a2=5+19=24
Para n=3:
A(3)=a2=24, B(3)=3cdot5+4cdot19=15+76=91, a3=24+91=115
Para n=4:
A(4)=a3=115, B(4)=3cdot24+4cdot91=72+364=436, a4=115+436=551

Resposta

551 (alternativa a)

Exercícios de Livros Relacionados