\hline
QUESTÃO & & Valor: 1,00 \
\hline \multicolumn{3}{|c|}{O conjunto
está contido em
e tem a seguinte propriedade: para todos os
,
é múltiplo de
. Qual é a quantidade máxima de elementos que
pode ter? Justifique.} \
\hline \multicolumn{3}{|c|}{O conjunto
Passo 1
Vou listar claramente o que o enunciado dá e o que pede.
- O universo é
. -
é um subconjunto de com a seguinte propriedade: para todos com , o número é múltiplo de . Em símbolos: se e então . - Pergunta: qual é a quantidade máxima de elementos que
pode ter? (queremos o maior possível e justificativa).
Passo 2
Primeira observação útil (e fácil): elementos distintos de
são coprimos entre si.
Prova: tomemos
com
. Sabemos que
. Se um inteiro
fosse divisor comum de
e
, então
divid gls dois números
e
, logo dividiria a diferença
, o que é impossível. Portanto
. Como
eram quaisquer dois elementos distintos em
, concluímos que os elementos de
são mutuamente coprimos (pairwise coprime).
Essa propriedade é importante porque força que diferentes elementos usem fatores primos distintos (exceto o
, que é coprimo com tudo).
Passo 3
Organizamos os elementos de
em ordem crescente:
onde
é o número de elementos. Pela propriedade do enunciado, para todo
vale
. Em particular, para cada
temos
. Como os
são coprimos entre si (Passo 2) e cada um divide
, segue que o produto
divide
. Portanto
Logo uma desigualdade chave é
Essa desigualdade nos dá um limite superior para
: para termos muitos elementos em
o produto dos primeiros
(os menores) deve caber em
. Para maximizar
queremos minimizar esse produto possível, dada a restrição de que os fatores são positivos, distintos e pairwise coprime.
Passo 4
Qual é o menor possível para o produto
dado que os
são inteiros distintos e pairwise coprime? A estratégia para minimizar o produto é escolher os menores inteiros possíveis que sejam mutuamente coprimos. É sempre vantajoso incluir
porque
é coprimo com tudo e não aumenta o produto. Para os demais termos
, cada um precisa ter um primo distinto em sua fatoração (senão dois deles teriam um divisor primo em comum). Assim, para minimizar o produto devemos tomar esses termos como os menores primos possíveis. Portanto, o produto mínimo para
fatores é obtido tomando
(ou seja,
e os menores primos distintos).
Calculemos cumulativamente até ultrapassar
:
Portanto o produto de
números (contando o
e os quatro primeiros primos
) já é
, mas se tentássemos ter
números diferentes e pairwise coprime (ou seja,
fatores) o menor produto possível seria
, o que viola a desigualdade do Passo 3. Assim não é possível ter
. Concluímos que
Portanto o tamanho máximo possível de
é no máximo
.
Passo 5
Agora precisamos mostrar que isso é atingível: construir explicitamente um conjunto
com
elementos que satisfaça a propriedade. Vou construir uma sequência crescente
que cumpre
para todo
.
Escolha:
Vou explicar como esses números foram escolhidos e verificar a propriedade.
Construção (intuição): escolho iterativamente
como um múltiplo do MMC (ou do produto, já que os termos anteriores serão coprimos) dos
, e escolho o menor múltiplo que seja maior que
. Assim garanto que para todo
vale
, isto é
, que é exatamente a exigência para
.
Verificação passo a passo:
-
é múltiplo de . -
é múltiplo de , logo e . -
é múltiplo de , logo . -
é múltiplo de , logo . -
é múltiplo de , logo .
Assim, para todo
temos
. Em palavras: cada elemento anterior divide todos os
dos posteriores. Portanto a condição do enunciado é satisfeita por todos os pares ordenados
.
Também verifique que todos os
estão em
:
, e os demais são bem menores; logo
.
Portanto existe
com
elementos que satisfaz a condição, então o limite
do Passo 4 é atingido.
Passo 6
Resumo final do argumento (curtinho):
- Mostramos que elementos de
são pairwise coprime. - Assim o produto dos
menores elementos divide , dando . - O menor produto possível para
inteiros distintos coprimos (incluindo ) excede já quando . Logo . - Construímos explicitamente um conjunto de
elementos que funciona, então é o máximo alcançável.
Resposta
6