(Olimpíada da Argentina-01) Carlos escreve a lista de todos os números naturais menores que 10000 que têm exatamente dois digitos 1 consecutivos. (Por exemplo. 113, 5112, 1181 estão na lista de Carlos, porém 1312, 2111 no estão na lista de Carlos.) Achar quantos números tem a lista de Carlos.
Solução:
Os números devem ser de uma das formas: 11 yz , y 11 z ou yzll.
Analisemos cada uma:
i) Ilyz: 9 maneiras de escolher y (não pode ser igual a l) e 10 maneitas de escolher
(sem restrições)
possibilidades
ii) y llz: 9 maneiras de escolher y (năo pode valer 1) e 9 maneiras de escolher
(nào pode ser igual a 1)
possibilidades
iii) yzl1: 10 maneiras de escolher y (sem restrições, pode até valer 0) e 9 maneiras de escolher
(não pode ser igual a 1 )
possibilidades
Analisemos cada uma:
i) Ilyz: 9 maneiras de escolher y (não pode ser igual a l) e 10 maneitas de escolher
ii) y llz: 9 maneiras de escolher y (năo pode valer 1) e 9 maneiras de escolher
iii) yzl1: 10 maneiras de escolher y (sem restrições, pode até valer 0) e 9 maneiras de escolher
Passo 1
O enunciado pede a quantidade de números naturais menores que
que contêm exatamente dois dígitos
consecutivos — ou seja, há uma única ocorrência da substring “11” e ela não faz parte de uma sequência maior de
s. O conteúdo envolve contagem de sequências de dígitos com restrições, e vamos modelar cada número como uma palavra de comprimento 4 sobre o alfabeto
(usando zeros à esquerda) para uniformizar a análise por posições.
Passo 2
Denotemos um número genérico pelas posições
. Queremos contar as palavras em que exatamente um par adjacente
ocorre, para
, e que não haja nenhum outro par “11” em posições distintas. Vamos tratar caso a caso para
.
Passo 3
Caso
: fixamos
Para não formar outro “11” em
nem em
, basta exigir
Assim
tem
opções e
tem
. Total de casos:
Passo 4
Caso
: fixamos
Para não ter “11” em
nem em
, impomos
Logo
tem
opções e
tem
. Total de casos:
Passo 5
Caso
: fixamos
Para evitar “11” em
, basta
Assim
tem
opções e
tem
. Total de casos:
Passo 6
Somando os três casos disjuntos, obtemos