n 11.05.04 12:48, Frederico Reis Marques de Brito at [EMAIL PROTECTED] wrote:
> Bom, dessa vez o resultado é verdadeiro. > Provar que dados 55 números inteiros entre 1 e 100, incluindo estes, > existem dois cuja diferença é exatamente 12. > Um abraço a todos, > Fred. > > De fato, basta escolher apenas 53 numeros do conjunto {1,2,...,100}. A demonstracao eh a mesma. Reduzimos os 53 numeros escolhidos mod 12 e os distribuimos por dentre as 12 classes de congruencia mod 12. Como 12*4 = 48 < 53, teremos os seguintes casos: Caso 1: uma das classes de congruencia mod 12 tem pelo menos 6 elementos. Caso 2: nenhuma classe de congruencia mod 12 tem mais do que 5 elementos. ----- Caso 1: Chamemos os 6 menores elementos da tal classe de: m, m+12*a, m+12*(a+b), m+12*(a+b+c), m+12*(a+b+c+d), m+12*(a+b+c+d+e), onde m, a, b, c, d, e sao inteiros positivos. Se a, b, c, d, e forem todos >= 2, entao teremos: m + 12*(a+b+c+d+e) >= m + 12*10 = m + 120 ==> contradicao, pois m + 12*(a+b+c+d+e) <= 100. Logo, um dentre a, b, c, d, e eh igual a 1. ----- Caso 2: Nesse caso, teremos pelo menos 5 classes de congruencia mod 12 com 5 elementos cada, pois se tivessemos apenas 4, entao 4*5 + (12-4)*4 = 52 < 53. Consideremos o menor elemento de cada uma das 5 classes com 5 elementos cada. Obviamente, estes menores elementos serao todos distintos, de forma que um deles, digamos n, serah >= 5. Assim, os elementos da classe de n serao: n, n + 12*a, n + 12*(a+b), n + 12*(a+b+c), n + 12*(a+b+c+d), onde a, b, c, d sao inteiros positivos. Se a, b, c, d, e forem todos >= 2, entao teremos: n + 12*(a+b+c+d) >= 5 + 12*8 = 101 ==> contradicao, pois n + 12*(a+b+c+d) <= 100. Logo, um dentre a, b, c, d eh necessariamente igual a 1. **** Juntamente com exemplo que eu dei antes, resolvemos o seguinte problema mais geral: Achar o menor inteiro N tal que se escolhermos quaisquer N elementos do conjunto {1,2,...,100}, teremos sempre, dentre os N escolhidos, dois cuja diferenca eh 12. Resposta: N = 53. []s, Claudio. ========================================================================= 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 =========================================================================