1)(HUNGRIA)
Sejam n um número natural e f(n) o número de zeros que
aparece na representação decimal de n. Por exemplo f(23) = 0,
f(100) = 2, f(1989)
= 0, f(105) = 1 etc.
Considerando
2^f(i) como sendo "2 elevado a f(i)", Calcule o valor da
expressão
E = 2^f(1) +
2^f(2) + 2^f(3) + ...+ 2^f(999.999.999)
Inicialmente, observe que:
E = N(0)*2^0 + N(1)*2^1 + N(2)*2^2 + ... +
N(8)*2^8
onde N(s) = número de inteiros positivos de
9 algarismos ou menos que têm "s" zeros ( 0 <= s <= 8 ) em sua
representação decimal.
A fim de avaliar N(s), definamos:
N(r,s) = número de inteiros positivos de "r"
algarismos ( 1 <= r <= 9 ) que têm "s" zeros ( 0 < = s
<= r-1 ) em sua representação decimal
Cálculo do valor de N(r,s):
Escolha do algarismo da primeira posição
(tem de ser <> 0):
9
Escolha de s das r-1 posições para os zeros:
C(r-1,s)
Escolha dos algarismos para as r-s-1 posições
remanescentes (também <> 0): 9^(r-s-1)
Assim: N(r,s) = 9 * C(r-1,s) *
9^(r-s-1) = C(r-1,s) * 9^(r-s)
Agora, N(s) = N(s+1,s) + N(s+2,s) + ... + N(9,s)
=
= C(s,s)*9^(s+1-s) + C(s+1,s)*9^(s+2-s) + ... +
C(8,s)*9^(9-s) =
= C(s,s)*9 + C(s+1,s)*9^2 + ... +
C(8,s)*9^(9-s) =
= 9 * [ C(s,s) + C(s+1,s)*9 + C(s+2,s)*9^2 + ...
+ C(8,s)*9^(8-s) ]
Tenho certeza de que deve haver uma fórmula
macetosa para a soma entre colchetes, mas achei mais fácil usar uma planilha.
Assim:
N(0) = 9 * [ 1 + 9 + 9^2 + ... + 9^8 ] = 9 *
(9^9 - 1) / 8 = 435.848.049
N(1) = 81.367.044
N(2) = 46.039.364
N(3) = 31.966.254
N(4) = 4.374.414
N(5) = 383.220
N(6) = 20.988
N(7) = 657
N(8) = 9
Substituindo estes valores na expressão para E em
função dos N(s), teremos:
E = 2.122.152.921 = 3^2 * 7 * 19 *
1.772.893
Curioso é que, mesmo com uma fórmula para a soma,
este problema ainda envolve uma quantidade razoável de contas braçais -
estranho para um problema de olimpíada.
É claro que pode haver alguma solução "mágica"
que não envolve conta nenhuma.....apesar de a fatoração de E não dar nenhuma
indicação disso.