Re: [obm-l] Prova da IMO - Primeiro dia

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

   Oi Domingos et al,
   Essa eu fiz assim: se 1<=i<j então |a_i-a_j|<j, senão, fazendo
n=|a_i-a_j|, temos 1<=i<j<=n mas a_i e a_j deixam o mesmo resto na divisão
por n. Assim, para todo n>=1, {a_1,a_2,...,a_n} tem que ser um "intervalo",
isto é, um conjunto de n inteiros consecutivos (com efeito, pelo fato acima, 
a diferença entre o menor e o maior desses números é menor que n, e eles são
todos distintos). Como uma união crescente de "intervalos" de inteiros que é 
ilimitada dos dois lados tem que o conjunto de todos os inteiros, acabou.

>
>
>>2. Seja a_1,a_2,... uma seqüência de inteiros com
>>infinitos termos positivos e negativos. Suponha que
>>para todo n inteiro positivo os números
>>a_1,a_2,...,a_n deixam n restos diferentes na divisão
>>por n.
>>
>>Prove que todo inteiro aparece exatamente uma vez na
>>seqüência a_1,a_2,...
>>
>>  
>>
>Achei este legal, note que o enunciado é levemente ambíguo, pois devemos 
>dizer que há infinitos termos positivos e infinitos termos negativos, 
>caso contrário, a sequüência dos números naturais positivos ordenados 
>claramente satisfaz a propriedade e não contém nenhum negativo.
>
>--- x ---
>
>Por conveniência, chame de P a propriedade do enunciado
>Seja S = {s_1, s_2, ...} uma seqüência que satisfaz P. Sem perda de 
>generalidade, podemos supor que 0 está em S. Basta observar que S + a = 
>{s_1 + a, s_2 + a, ...} também satisfaz P.
>
>Vamos mostrar que, para todo n >= 0, existe N tal que todos os valores 
>{-n, 1-n, ..., -1, 0, 1, ..., n} aparecem em {s_1, ..., s_N}.
>Por hipótese, o caso n = 0 está ok. Vamos provar que se vale para n-1 
>então vale para n.
>Existe N' tal que {1-n, ..., 0, ..., n-1} aparecem em {s_1, ..., s_N'}. 
>Tome N > N' > 2n e considere o único s_i em {s_1, ..., s_N} tal que s_i 
>~ n (mod N), se s_i = n, paramos por aqui. Senão
>    - caso s_i = A + n com N|A e A >= N temos, claramente que {s_1, ..., 
>s_{A+n}} contém dois valores que são 0 mod A + n, a saber, 0 e s_i = A + 
>n, o que não pode ocorrer.
>    - caso s_i = n - A, com N|A e A > N, então |s_i| = A - n >= N e 
>novamente {s_1, ..., s_{A-n}} contém dois 0 mod (A-n).
>    - caso s_i = n - N: neste caso não temos como fazer a mesma 
>asserção, mas note que N pode ser qualquer valor > N' e se cairmos 
>sempre neste caso para qualquer escolha de N vamos exibir uma 
>contradição* em S.
>Para s_i ~ -n (mod N) o argumento é análogo ao acima.
>
>* Suponha que para todo N > N' tenhamos n - N pertence a {s_1, ..., 
>s_N}, um simples argumento de contagem mostra que há infinitos números 
>negativos em S, mas não podemos ter infinitos números *positivos* em S.
>
>Abraços.
>
>
>
>
>=========================================================================
>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
>=========================================================================
>

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