Escolha dentre os números \{1,2, \ldots, 200\}, 101 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 101 números distintos de \{1,2,\dots,200\}, mostremos que sempre existem dois escolhidos, digamos a e b, 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 2 e parte ímpar.

Passo 2

Para cada inteiro m em \{1,2,\dots,200\}, podemos escrever de forma única
m = 2^k \, d,
onde k\ge0 é um inteiro e d é ímpar. Chamemos d de “parte ímpar” de m. Por exemplo, se m=12 então 12=2^2\cdot3 e a parte ímpar é 3.

Passo 3

Note que as possíveis partes ímpares d vêm do conjunto \{1,3,5,\dots,199\}, que contém exatamente 100 elementos. Logo, a função que associa a cada m sua parte ímpar assume no máximo 100 valores diferentes.

Passo 4

Como escolhemos 101 números dentre os 200, pelo Princípio da Casa dos Pombos existem dois desses números, digamos m_1 e m_2, que têm a mesma parte ímpar. Ou seja,
m_1 = 2^{k_1} d \quad\text{e}\quad m_2 = 2^{k_2} d
com d ímpar e k_1,k_2\ge0.

Passo 5

Sem perda de generalidade, suponha k_1\le k_2. Então
m_2 = 2^{k_2} d = 2^{k_2 - k_1}\,\bigl(2^{k_1}d\bigr) =2^{k_2-k_1}\,m_1.
Como k_2-k_1 é inteiro não–negativo, segue que m_2 é múltiplo de m_1. Portanto um dos dois divide o outro.

Resposta

Entre quaisquer 101 números escolhidos em \{1,2,\dots,200\} existem sempre dois tais que um divide o outro.

Exercícios relacionados