Questão 9

Enunciado

Quantos números, de 1 a 1983, podem ser escritos como soma de duas ou mais potências distintas de 3 ?

Passo 1

O enunciado pede quantos inteiros de 1 a 1983 podem ser escritos como soma de duas ou mais potências distintas de 3. O conteúdo principal é observar que toda soma de potências distintas de 3 corresponde a um número cuja representação em base 3 tem apenas algarismos 0 ou 1, com pelo menos dois dígitos 1.

Passo 2

Identificamos quais potências de 3 são úteis. Como
3^7 = 2187 > 1983,
as potências válidas são
3^0,3^1,3^2,3^3,3^4,3^5,3^6,
totalizando 7 valores: 1,3,9,27,81,243,729.

Passo 3

Note que a soma de todas essas 7 potências é
1+3+9+27+81+243+729 = 3^7-13-1 = 2187-12 = 1093,
que fica abaixo de 1983. Logo, toda soma de qualquer subconjunto dessas potências também é <=1093 e, portanto, pertence ao intervalo de 1 a 1983.

Passo 4

Cada subconjunto de tamanho k (com k>=2) dá um número distinto. Há 2^7 subconjuntos no total, dos quais 1 é o vazio e 7 têm tamanho 1. Assim, o número de subconjuntos de tamanho pelo menos 2 é
2^7 - 1 - 7 = 128 - 8 = 120

Resposta

120

Exercícios relacionados