Escolha dentre os números
números ao acaso. Prove que entre os escolhidos, há dois números tais que um deles divide o outro.
Passo 1
O enunciado pede que, ao escolhermos
números distintos de
, mostremos que sempre existem dois escolhidos, digamos
e
, tais que um divide o outro. O conteúdo principal é o Princípio da Casa dos Pombos (Princípio de Dirichlet) aliado a uma decomposição única de cada inteiro em fatoração por potências de
e parte ímpar.
Passo 2
Para cada inteiro
em
, podemos escrever de forma única
onde
é um inteiro e
é ímpar. Chamemos
de “parte ímpar” de
. Por exemplo, se
então
e a parte ímpar é
.
Passo 3
Note que as possíveis partes ímpares
vêm do conjunto
, que contém exatamente
elementos. Logo, a função que associa a cada
sua parte ímpar assume no máximo
valores diferentes.
Passo 4
Como escolhemos
números dentre os
, pelo Princípio da Casa dos Pombos existem dois desses números, digamos
e
, que têm a mesma parte ímpar. Ou seja,
com
ímpar e
.
Passo 5
Sem perda de generalidade, suponha
. Então
Como
é inteiro não–negativo, segue que
é múltiplo de
. Portanto um dos dois divide o outro.
Resposta
Entre quaisquer
números escolhidos em
existem sempre dois tais que um divide o outro.