Re: [obm-l] Novamente as gavetas

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 11.05.04 12:48, Frederico Reis Marques de Brito at fredericor@hotmail.com
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
=========================================================================