Prove que, entre 7 reais
, podemos escollher
e
, tais que
.
23) a) Dado um conjunto de 101 inteiros positivos, nenhum dos quais excede 200, mostre que pelo menos um membro deste conjunto deve dividir outro membro do conjunto.
23) a) Dado um conjunto de 101 inteiros positivos, nenhum dos quais excede 200, mostre que pelo menos um membro deste conjunto deve dividir outro membro do conjunto.
Passo 1
No primeiro problema, temos sete números reais
e queremos mostrar que existem índices
tais que
O método é usar o princípio da casa dos pombos aplicado aos arctangentes e a fórmula da tangente da diferença de ângulos.
Passo 2
Definimos para cada
o ângulo
onde
. Como temos 7 ângulos nesse intervalo de comprimento
, se o dividirmos em 6 subintervalos iguais de comprimento
, por princípio da casa dos pombos existem
tais que
Passo 3
Usamos a identidade de tangente da diferença:
Como
, o denominador
é positivo e
fica concorde em sinal com
. Basta então escolher
de modo que
, garantindo
. Além disso,
Passo 4
Concluímos que existem
tais que
Passo 5
No segundo problema, temos um conjunto de 101 inteiros positivos, cada um
. Queremos provar que algum elemento divide outro. Vamos usar fatoração em potências de 2 e o princípio da casa dos pombos para as partes ímpares.
Passo 6
Para cada número
do conjunto, escrevemos
onde
é a maior potência de 2 que divide
e
é ímpar. Note que
e
só pode assumir valores ímpares em
, ou seja, 100 possibilidades.
Passo 7
Temos 101 números e apenas 100 valores possíveis para a parte ímpar
. Pelo princípio da casa dos pombos, existem dois números
e
com a mesma parte ímpar
. Sem perda, suponha
. Então
logo
divide
.
Passo 8
Portanto, dentro de qualquer conjunto de 101 inteiros positivos
há sempre algum elemento que divide outro.
Resposta
Em qualquer conjunto de 101 inteiros positivos não superiores a 200, existe pelo menos um elemento que divide outro.