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

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

estranho... parece que a mensagem não foi... estou mandando novamente,
desculpe se ela aparecer duas vezes!


> 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
=========================================================================