.Problemão: Somas de potências de 3

Problema
(Indicado a partir do 1º ano do E. M.)

Quantos números de [tex]1[/tex] a [tex]2019[/tex] podem ser escritos como soma de duas ou mais potências distintas de [tex]3[/tex]?

Solução

As primeiras potências de [tex]3[/tex] são:

  • [tex]3^{0}=1[/tex], [tex]3^{1}=3[/tex], [tex]3^{2}=9[/tex], [tex]3^{3}=27[/tex], [tex]3^{4}=81[/tex], [tex]3^{5}=243[/tex], [tex]3^{6}=729[/tex], [tex]3^{7}=2187 \gt 2019[/tex].

Assim, os números buscados são somas de potências pertencentes ao conjunto [tex]A=\{3^0, 3^1, 3^2,3^ 3,3^ 4, 3^5, 3^6\}[/tex].
Observe que qualquer subconjunto de [tex]A[/tex], com dois ou mais elementos, poderá ser utilizado para se obter um dos números procurados.
Por exemplo, o subconjunto [tex]\{3^0, 3^1, 3^4, 3^5\}[/tex] corresponde ao número [tex]3^0+3^1+3^4+3^5=328[/tex].
Vamos então trocar o processo de contar números que satisfaçam as condições exigidas por contar subconjuntos de [tex]A[/tex] que gerem números que satisfaçam essas condições.

Vamos lá!

O conjunto [tex]A[/tex] tem [tex]2^{7}[/tex] subconjuntos, dos quais um é o vazio e sete têm um só elemento; os demais fornecerão os números procurados.
Dessa forma,

  • há [tex]2^{7}- 7-1=120[/tex] números entre [tex]1[/tex] e [tex]2019[/tex] que podem ser escritos como soma de duas ou mais potências distintas de [tex]3[/tex].

Pronto?

Ainda não. Rigorosamente, temos que justificar algumas passagens que fizemos:

1) Qualquer escolha de potências resultará, de fato, em um número maior ou igual a [tex]1[/tex] e menor ou igual a [tex]2019[/tex]?
Isto é simples de verificar, pois [tex]3^0+3^1+3^2+3^3+3^4+3^5+3^6=1093[/tex] é a maior das somas possíveis, [tex]3^0+3^1=4[/tex] é a menor e [tex]1 \lt 4\lt 1093 \lt 2019.[/tex]
2) Quaisquer duas escolhas de potências fornecem números distintos.
Isto é verdade, mas pode ser mais difícil de provar. Consulte, clicando no botão abaixo.

Suponha que duas escolhas distintas de potências produzam o mesmo número:
[tex]3^{a_1}+3^{a_2}+\cdots+3^{a_n}=3^{b_1}+3^{b_2}+\cdots+3^{b_m}[/tex], com os expoentes colocados em ordem crescente, isto é, [tex]0\leq a_1\lt a_2\lt \cdots \lt a_n\leq 6[/tex] e [tex]0\leq b_1\lt b_2\lt \cdots \lt b_m\leq 6[/tex].
Inicialmente, cancelemos todos os termos que aparecem em ambos os lados da igualdade, obtendo
[tex]3^{a’_1}+3^{a’_2}+\cdots+3^{a’_{n’}}=3^{b’_1}+3^{b’_2}+\cdots+3^{b’_{m’}}[/tex], onde todas as potências são distintas e [tex]0\leq a’_1\lt a’_2\lt \cdots \lt a’_{n’}\leq 6[/tex] e [tex]0\leq b’_1\lt b’_2\lt \cdots \lt b’_{m’}\leq 6[/tex].
A maior potência será [tex]3^{a’_{n’}}[/tex] ou [tex]3^{b’_{m’}}[/tex]. Suponha que seja [tex]3^{a’_{n’}}[/tex] (não faz diferença supor assim). Veja que [tex]3^{a’_1}+3^{a’_2}+\cdots+3^{a’_{n’}}=3^{b’_1}+3^{b’_2}+\cdots+3^{b’_{m’}}[/tex], então [tex]3^{a’_{n’}}\leq 3^{b’_1}+3^{b’_2}+\cdots+3^{b’_{m’}}[/tex], isto é, certa potência de [tex]3[/tex] é menor ou igual à soma de diversas potências de [tex]3[/tex] menores do que ela.
A questão é que isso não pode ocorrer! A soma de potências de [tex]3[/tex] menores do que certa potência sempre é menor do que esta potência! De fato,
[tex]3^{b’_1}+3^{b’_2}+\cdots+3^{b’_{m’}}\leq 3^0+3^1+\cdots+ 3^{b’_{m’}}= \dfrac{3^0(3^{b’_{m’}+1}-1)}{3-1}=\dfrac{3^{b’_{m’}+1}-1}{2}\lt 3^{b’_{m’}+1}\leq 3^{a’_{n’}}[/tex], onde aqui usamos a fórmula da soma de uma PG finita:
[tex]a_1+a_1q+\cdots a_1q^{n}=\dfrac{a_1(q^{n+1}-1)}{q-1}[/tex].

Na verdade, o resultado de que somas distintas de potências de mesma base resultam em números distintos é sempre válido.

Solução elaborada pelos Moderadores do Blog.

Link permanente para este artigo: http://clubes.obmep.org.br/blog/problemao-somas-de-potencias-de-3/