Consegui fazer algumas coisas em cima disso.
> Seja n>4 um inteiro.
> Prove que para quaisquer numeros a(i), 1<=i<=n, satisfazendo
>
> 1<=a(1)>
> existem i e j, i>
> M.M.C.(a(i),a(j))<=3n+6.
É um fato conhecido que se tivermos n+1 elementos de um conjunto A
contido em {1, ..., 2n} então há dois números a, b tais que a divide b.
Neste caso é evidente que o mmc(a, b) = b <= 2n.
A demonstração disso é bem bonitinha:
Todo elemento a de A pode ser escrito como a = 2^k * m onde m é ímpar (m
está em {1, 3, ..., 2n-1}). Como há n+1 elementos em A, dois deles tem
mesma parte ímpar, e isso mostra que um divide o outro.
No caso de n elementos, se não podemos repetir nenhum elemento ímpar,
então todos os ímpares possíveis devem ser usados, ou seja, devemos ter
A = {2^k_1, 2^k_2 * 3, 2^k_3 * 5, ..., 2^k_n * (2n-1)}
Claramente os elementos a = 2^k * m, para os quais n <
m < 2n, tem
expoente k = 0, ou seja, {2n - 1, 2n - 3, ..., r} estão em A, onde n < r
< n + 3.
Tome m como o menor múltiplo de 3, ímpar, maior que 3n/2 (note que m
está em A).
(Ou seja, m=6x+3 com x sendo o menor natural tal que x>\frac{n-2}{4}).
Pela nossa escolha m/3 é um inteiro ímpar e 4m/3 > 2n. Sendo assim, o
elemento 2^k * (m/3) que está em A é tal que 0 <= k < 2.
Veja que mmc(2^k * m/3, m) = 2^k * m <= 2m.
Dá pra ver que 2m = 3n + O(1). Agora tem que ver como trocar esse O(1)
pela constante do enunciado, mas isso fica pra quem tiver paciência.
(Basta provar que 2m<3n+6. E isto equivale a n>4x. Temos que x e o menor tal que 4x>n-2. Logo 4x>n-2>4x-4, e assim n>4x-2.Ih!!!).
[ ]'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
=========================================================================