[obm-l] Re: [obm-l] Números inteiros e probabilidade

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Sat, Feb 28, 2004 at 06:51:31PM -0300, Rafael wrote:
> "Sejam três inteiros escolhidos ao acaso, a probabilidade de que não haja
> fator comum que os divida é...?"

O problema se generaliza naturalmente para n inteiros.
A resposta no caso geral é 1/zeta(n) e no caso que você enunciou
é 1/zeta(3) ~=  0.8319073727. Aqui
zeta(s) = 1 + 1/2^s + 1/3^s + 1/4^s + 1/5^s + ...
é a função zeta de Riemann. Acredita-se que zeta(3) é um número irracional
que não admite nenhuma expressão simples em termos de outras constantes
como pi e e, mas tanto quanto eu saiba, ninguém sabe provar nada disso.
Por outro lado zeta(2) = pi^2/6, zeta(4) = pi^4/90, zeta(6) = pi^6/945
e zeta(2n) é sempre um múltiplo racional de pi^(2n).

Antes de mais nada vamos ter certeza de que concordamos com a interpretação
do problema. Definimos Xn, um subconjunto de Z^n, da seguinte maneira:
(a1,a2,...,an) pertence a Xn se e somente se mdc(a1,a2,...,an) = 1, i.e.,
se e somente se o único inteiro positivo d para os qual a1/d, a2/d, ... an/d
são todos inteiros é 1. Queremos provar que a densidade de Xn é 1/zeta(n).
A densidade de um subconjunto Y de Z^n é definida pelo limite:

densidade(Y) = lim_{r -> infinito} |Y interseção B(r)|/|Z^n interseção B(r)|

onde B(r) é a bola de raio r centrada no origem. Note que a densidade pode
não existir: numa solução completa do problema, precisaríamos provar que
a densidade de Xn existe para todo n.

Eu não vou provar que a densidade existe mas vou provar que se ela existe
ela vale 1/zeta(n). Defina dXn = { dv, v em Xn } = { v em Z^n, mdc(v) = d }.
Assim dXn é semelhante a Xn, mas expandido por um fator d. Não é difícil
ver que densidade(dXn) = (1/d^n) * densidade(Xn). Mas Zn - {0}, que tem
densidade 1, é a união disjunta dos dXn, d um inteiro positivo.
Assim
1 = densidade(Z^n - {0}) = densidade(Xn) + densidade(2Xn) + densidade(3Xn) +...
= (1 + 1/2^n + 1/3^n + ... ) * densidade(Xn) = zeta(n) * densidade(Xn)
ou
densidade(Xn) = 1/zeta(n).

[]s, N.



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