Mostre que entre sete inteiros positivos distintos menores do que 127 podemos escolher um par, digamos
, tal que
.
Soluçāo:
Notemos inicialmente que
.
Podemos dividir os 126 números de 1 até 126 da seguinte forma:
Como temos 6 conjuntos e 7 inteiros para escolher, teremos pelo menos 2 números. digamos x e y, de um mesmo conjunto. É imediato para estes dois números do mesmo conjunto, admitindo
. que ocore
.
Soluçāo:
Notemos inicialmente que
Podemos dividir os 126 números de 1 até 126 da seguinte forma:
Passo 1
O enunciado pede para mostrar que, dada qualquer escolha de sete inteiros positivos distintos menores que
, sempre existe um par
com
tal que
O conteúdo principal usado será o Princípio da Casa dos Pombos (pigeonhole) e uma partição adequada do conjunto
.
Passo 2
Vamos particionar o conjunto
em seis blocos cujos comprimentos dobram a cada etapa:
Passo 3
Em cada bloco, se escolhermos dois elementos
, então o maior elemento do bloco é no máximo o dobro do menor. Por exemplo, em
temos
. Em geral, para qualquer bloco,
Passo 4
Como há
blocos e estamos escolhendo
inteiros distintos, pelo Princípio da Casa dos Pombos há pelo menos dois números, digamos
e
com
, que caem no mesmo bloco.
Passo 5
Esses
e
satisfazem imediatamente
o que conclui a demonstração.
Resposta
Entre sete inteiros positivos distintos menores que
podemos sempre encontrar
tais que