[obm-l] Cone Sul - sol. da 03

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Olá, resolvi o problema 3, vou dar uma breve descrição do que eu fiz. Não
estou com tempo para passar tudo a limpo então a mensagem vai 'a la
Dirichlet'.

Defina f(k) := soma dos dígitos de k em base 10.
1. Mostre que se 0 <= a <= 9 e 0 <= b < 10^n, então f(a.10^n + b) = f(a) +
f(b) e f(2a.10^n + 2b) = f(2a) + f(2b).

Defina X(n, i) = #{x | 0 <= x < 10^n, f(x) - f(2x) = i}.

2. A partir de (1), mostre uma recorrência de X(n+1, i) em função dos X(n,
j)'s.

dica: X(n+1, i) = #{a.10^n + b | 0 <= a <= 9, 0 <= b < 10^n, f(a.10^n + b) -
f(2a.10^n + 2b) = f(a) - f(2a) + f(b) - f(2b) = i}.

3. Mostre que X(n, i) é simétrica em relação a X(n, 0), ou seja X(n, -i) =
X(n, i).

4. Mostre que X(n, i) >= X(n, i + 1)  para i >= 0.

5. Verifique que X(n, 0) < 10^(n - 1) para n >= 3.

6. Deduza que C_n > (4/9).10^n para n >= 3 a partir de 5 e prove os casos n
= 1,2 no braço.

[ ]'s

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================