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

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

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