Mostre que em todo subconjunto de \{1,2, \ldots, 2 n\} com n+1 elementos há dois elementos neste subconjunto tais que um deles é múltiplo do outro. Dica:Use que todo número natural pode ser escrito na forma 2^{k} m, com m ímpar.

Passo 1

O enunciado pede para mostrar que em qualquer subconjunto de \{1,2,\dots,2n\} com n+1 elementos existem dois elementos em que um divide o outro. Para isso, vamos usar a decomposição de cada inteiro em potência de 2 vezes uma parte ímpar e, em seguida, o princípio da casa dos pombos.

Passo 2

Note que todo x\in\{1,2,\dots,2n\} pode ser escrito de forma única como
x = 2^k m,
onde k\ge0 e m é ímpar. Os possíveis valores de m são exatamente os n números ímpares de 1 até 2n, ou seja,
\{1,3,5,\dots,2n-1\}.

Passo 3

Ao escolher n+1 elementos em \{1,2,\dots,2n\}, temos n+1 decomposições 2^k m mas apenas n valores possíveis para a parte ímpar m. Pelo princípio da casa dos pombos, dois desses elementos compartilham o mesmo m. Denote-os por
a = 2^{k_1}m \quad\text{e}\quad b = 2^{k_2}m.

Passo 4

Sem perda de generalidade, suponha k_1\le k_2. Então
\frac{b}{a} = \frac{2^{k_2}m}{2^{k_1}m} = 2^{k_2-k_1}\in\mathbb{N},
o que significa que a divide b. Assim encontramos no subconjunto dois elementos em que um é múltiplo do outro.

Resposta

Em todo subconjunto de \{1,2,\dots,2n\} com n+1 elementos há dois elementos tais que um deles é múltiplo do outro.

Exercícios relacionados