Mostre que em todo subconjunto de
com
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
, com m ímpar.
Passo 1
O enunciado pede para mostrar que em qualquer subconjunto de
com
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
pode ser escrito de forma única como
onde
e
é ímpar. Os possíveis valores de
são exatamente os
números ímpares de
até
, ou seja,
Passo 3
Ao escolher
elementos em
, temos
decomposições
mas apenas
valores possíveis para a parte ímpar
. Pelo princípio da casa dos pombos, dois desses elementos compartilham o mesmo
. Denote-os por
Passo 4
Sem perda de generalidade, suponha
. Então
o que significa que
divide
. Assim encontramos no subconjunto dois elementos em que um é múltiplo do outro.
Resposta
Em todo subconjunto de
com
elementos há dois elementos tais que um deles é múltiplo do outro.