Re: [obm-l] Pra lembrar os velhos tempos... Um pouco de PCP

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

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