on 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. > > O contra-exemplo que eu tinha em mente era: 01,02,03,04,05,06,07,08,09,10,11,12, 25,26,27,28,29,30,31,32,33,34,35,36, 49,50,51,52,53,54,55,56,57,58,59,60, 73,74,75,76,77,78,79,80,81,82,83,84, 97,98,99,100. Obviamente, isso soh prova que podemos escolher 52 numeros sem que tenhamos dois cuja diferenca eh 12. ***** Agora, a solucao: Vamos reduzir os 55 numeros escolhidos mod 12 e distribui-los por dentre as 12 classes de congruencia mod 12. Como 12*4 = 48 < 55, 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 e acabou. ----- Caso 2: Nesse caso, teremos pelo menos 7 classes de congruencia mod 12 com 5 elementos cada, pois se tivessemos apenas 6, entao 6*5 + (12-6)*4 = 54 < 55. Consideremos o menor elemento de cada uma das 7 classes com 5 elementos cada. Obviamente, estes menores elementos serao todos distintos, de forma que um deles, digamos n, serah >= 7. 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) >= 7 + 12*8 = 103 ==> contradicao, pois n + 12*(a+b+c+d) <= 100. Logo, um dentre a, b, c, d eh necessariamente igual a 1 e tambem acabou. []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 =========================================================================
