(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 20002001 cujos dígitos, em base 10, são apenas 0 ou 2. Em outras palavras, queremos todos os números formados só por algarismos \{0,2\}, excluindo o zero, e que sejam \le20002000.

Passo 2

Primeiro, contamos os números com até 7 dígitos. Se um número tem k dígitos, 1\le k\le7, então o dígito mais significativo deve ser 2 (não pode ser zero) e cada um dos k-1 dígitos restantes pode ser 0 ou 2. Logo, para cada k
2^{\,k-1}
possibilidades. Somando de k=1 a 7, obtemos
\sum_{k=1}^{7}2^{\,k-1}=2^{7}-1=127.

Passo 3

Agora, números de 8 dígitos formados por \{0,2\} e \le20002000. Escrevendo 20002000 como vetor de dígitos (2,0,0,0,2,0,0,0), fazemos posição a posição sob a condição “ \le”:
  1. Nas posições 1 a 4 só cabe a escolha forçada que mantêm igualdade até aí: (2,0,0,0).
  2. Na posição 5 o dígito pode ser 0 ou 2.
    • Se escolhermos 0<2, então as 3 posições finais podem ser livremente 0 ou 2, dando 2^3=8 números.
    • Se escolhermos 2=2, permanecemos “apertados” até a posição 5, mas nas posições 6,7,8 o dígito máximo permitido é 0, então há só 1 escolha (todas zero), correspondendo exatamente a 20002000.
      Total de 8 dígitos válidos: 8+1=9.

Passo 4

Somando as duas partes:
127 + 9 = 136.

Resposta

136

Exercícios de Livros Relacionados