20) Seja f: S = {2, 3, 4, 5, 6, ...} -> S a função que leva um número n no seu número de fatores primos. Por exemplo, f(6) = 2 e f(12) = f(8) = 3. Quanto vale lim[n->inf] (f(2) + f(3) + ... + f(n))/(n-1)?
A resposta é bonitinha quando f não conta os primos repetidamente...
Vamos usar aquele princípio básico da combinatória que nos ensina a contar a mesma coisa de duas maneiras distintas :-)
Note que f(2) + ... + f(n) é equivalente a Soma_{p primo} Piso{n/p}.
Para verificar isso, disponha caixas indexadas por todos os primos <= n. Olhe para cada elemento i <= n, colocando um marcador na caixa p em cada primo p que é divisor de i. É evidente que o número de marcadores de todas as caixas é f(2) + ... + f(n). Por outro lado, quantos marcadores teremos numa caixa p? Cada inteiro i <= n que é múltiplo de p colocou exatamente um marcador em tal caixa, logo temos Piso{n/p} marcadores em tal caixa.
Sempre que o termo "p" aparecer, fica implícito que p é primo, ok?
Como Piso{n/p} > n/p - 1, temos:
f(2) + ... + f(n) > Soma_{p <= n} [n/p - 1] = -pi(n) + n Soma_{p <=n} [1/p],
onde pi(n) é a função que conta o número de primos <= n.
Resultados clássicos nos grantem que:
i) pi(n) ~ n/(log n)
ii) Soma_{p <=n} [1/p] ~ log log n, logoSoma_{p <= n} [n/p - 1] ~ n[log log n - 1/(log n)].Isso prova que lim_{n -> oo} [f(2) + ... + f(n)]/n = oo. Como a nossa f tem valores sempre menores ou iguais aos valores da f do problema original, o resultado vale também para o problema original.
Se f conta os primos de forma repetida então a nossa contagem passa a ser
f(2) + ... + f(n) = Soma_{k = 0..oo} Soma_{p primo} Piso{n/p^k}.
Talvez alguém da lista tenha paciência de analisar assintoticamente o mostrinho...
[ ]'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 =========================================================================
