(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
a) 551
b) 552
c) 553
d) 554
e) 555
Passo 1
Resumindo: queremos formar senhas de 4 dígitos usando os algarismos
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
que não contêm “13”:
– : número de sequências de comprimento
que terminam em
.
– : número de sequências de comprimento
que terminam em algum dígito de
.
O total sem “13” é .
–
–
O total sem “13” é
Passo 3
Para estender uma sequência válida de tamanho
a
:
- Se quisermos terminar em
, podemos anexar 1 a qualquer sequência de tamanho . Logo,
- Se quisermos terminar em
, devemos evitar anexar 3 após uma sequência que já termina em 1. Há 3 escolhas 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,
Passo 4
Inicialmente, para
:
Logo
. Agora iteramos:
Para :
Para
Para
:
Para
:
Resposta
551
(alternativa a)