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