(Olimpiada da Estōnia-01) Quantos números inteiros positivos menores que 20002001 não contém outros algarismos distintos de 0 e 2 ?
Passo 1
O enunciado pede para contar todos os inteiros positivos menores que
cujos dígitos, em base 10, são apenas
ou
. Em outras palavras, queremos todos os números formados só por algarismos
, excluindo o zero, e que sejam
.
Passo 2
Primeiro, contamos os números com até 7 dígitos. Se um número tem
dígitos,
, então o dígito mais significativo deve ser
(não pode ser zero) e cada um dos
dígitos restantes pode ser
ou
. Logo, para cada
há
possibilidades. Somando de
a
, obtemos
Passo 3
Agora, números de 8 dígitos formados por
e
. Escrevendo
como vetor de dígitos
, fazemos posição a posição sob a condição “
”:
- Nas posições 1 a 4 só cabe a escolha forçada que mantêm igualdade até aí:
. - Na posição 5 o dígito pode ser
ou . - Se escolhermos
, então as 3 posições finais podem ser livremente ou , dando números. - Se escolhermos
, permanecemos “apertados” até a posição 5, mas nas posições 6,7,8 o dígito máximo permitido é , então há só 1 escolha (todas zero), correspondendo exatamente a .
Total de 8 dígitos válidos:.
- Se escolhermos
Passo 4
Somando as duas partes: