Seja n>4 um inteiro.
Prove que para quaisquer numeros a(i), 1<=i<=n, satisfazendo 1<=a(1)<a(2)<a(3)<a(4)<...<a(n)<=2*n
existem i e j, i<j, tais que 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).
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.
[ ]'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 =========================================================================
