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