FW: [obm-l] Novamente as gavetas

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

n 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.
> 
> 

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