Mostre que entre sete inteiros positivos distintos menores do que 127 podemos escolher um par, digamos x, y, tal que 1<\frac{y}{x} \leq 2.
Soluçāo:
Notemos inicialmente que 2^{7}=128=127+1.
Podemos dividir os 126 números de 1 até 126 da seguinte forma:
\begin{gathered} \{1,2\},\{3,4,5,6\},\{7,8,9,10,11,12,13,14\} .\{15,16, \ldots .30\} . \\\ \{31,32, \ldots, 62\},\{63,64, \ldots, 126\} \end{gathered}
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 \mathrm{y}>\mathrm{x}. que ocore 1<\frac{\mathrm{y}}{\mathrm{x}} \leq 2.

Passo 1

O enunciado pede para mostrar que, dada qualquer escolha de sete inteiros positivos distintos menores que 127, sempre existe um par (x,y) com x<y tal que
1 < \frac{y}{x} \le 2.
O conteúdo principal usado será o Princípio da Casa dos Pombos (pigeonhole) e uma partição adequada do conjunto \{1,2,\dots,126\}.

Passo 2

Vamos particionar o conjunto \{1,2,\dots,126\} em seis blocos cujos comprimentos dobram a cada etapa:
\{1,2\},\quad \{3,4,5,6\},\quad \{7,\dots,14\},\quad \{15,\dots,30\},\quad \{31,\dots,62\},\quad \{63,\dots,126\}.

Passo 3

Em cada bloco, se escolhermos dois elementos x<y, então o maior elemento do bloco é no máximo o dobro do menor. Por exemplo, em \{15,\dots,30\} temos 30 = 2\cdot 15. Em geral, para qualquer bloco,
y \le 2x \quad\Longrightarrow\quad 1 < \frac{y}{x} \le 2.

Passo 4

Como há 6 blocos e estamos escolhendo 7 inteiros distintos, pelo Princípio da Casa dos Pombos há pelo menos dois números, digamos x e y com x<y, que caem no mesmo bloco.

Passo 5

Esses x e y satisfazem imediatamente
1 < \frac{y}{x} \le 2,
o que conclui a demonstração.

Resposta

Entre sete inteiros positivos distintos menores que 127 podemos sempre encontrar x<y tais que
1 < \frac{y}{x} \le 2.

Exercícios de Livros Relacionados