\hline 8^{\mathrm{a}} QUESTÃO & & Valor: 1,00 \
\hline \multicolumn{3}{|c|}{O conjunto X está contido em S=\{1,2,3,4, \ldots, 2026\} e tem a seguinte propriedade: para todos os x, y \in X \operatorname{com} x<y, (y+1) é múltiplo de x. Qual é a quantidade máxima de elementos que X pode ter? Justifique.} \

Passo 1

Vou listar claramente o que o enunciado dá e o que pede.
  • O universo é S=\{1,2,3,\dots,2026\}.
  • X é um subconjunto de S com a seguinte propriedade: para todos x,y\in X com x<y, o número y+1 é múltiplo de x. Em símbolos: se x<y e x,y\in X então x\mid(y+1).
  • Pergunta: qual é a quantidade máxima de elementos que X pode ter? (queremos o maior possível |X| e justificativa).

Passo 2

Primeira observação útil (e fácil): elementos distintos de X são coprimos entre si.
Prova: tomemos x,y\in X com x<y. Sabemos que x\mid(y+1). Se um inteiro d>1 fosse divisor comum de x e y, então d divid gls dois números y e y+1, logo dividiria a diferença (y+1)-y=1, o que é impossível. Portanto \gcd(x,y)=1. Como x,y eram quaisquer dois elementos distintos em X, concluímos que os elementos de X são mutuamente coprimos (pairwise coprime).
Essa propriedade é importante porque força que diferentes elementos usem fatores primos distintos (exceto o 1, que é coprimo com tudo).

Passo 3

Organizamos os elementos de X em ordem crescente:
a_1<a_2<\cdots<a_k,
onde k=|X| é o número de elementos. Pela propriedade do enunciado, para todo i<j vale a_i\mid(a_j+1). Em particular, para cada i<k temos a_i\mid(a_k+1). Como os a_1,\dots,a_{k-1} são coprimos entre si (Passo 2) e cada um divide a_k+1, segue que o produto
P:=a_1\cdot a_2\cdots a_{k-1}
divide a_k+1. Portanto
P \le a_k+1 \le 2026+1=2027.
Logo uma desigualdade chave é
a_1 a_2\cdots a_{k-1} \le 2027.
Essa desigualdade nos dá um limite superior para k: para termos muitos elementos em X o produto dos primeiros k-1 (os menores) deve caber em 2027. Para maximizar k 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 a_1\cdots a_{k-1} dado que os a_i 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 1 porque 1 é coprimo com tudo e não aumenta o produto. Para os demais termos >1, 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 k-1 fatores é obtido tomando
a_1=1,\; a_2=2,\; a_3=3,\; a_4=5,\; a_5=7,\;\dots
(ou seja, 1 e os menores primos distintos).
Calculemos cumulativamente até ultrapassar 2027:
\begin{aligned} 1 &=1,\\\\ 1\cdot 2 &=2,\\\\ 1\cdot 2\cdot 3 &=6,\\\\ 1\cdot 2\cdot 3\cdot 5 &=30,\\\\ 1\cdot 2\cdot 3\cdot 5\cdot 7 &=210,\\\\ 1\cdot 2\cdot 3\cdot 5\cdot 7\cdot 11 &=2310>2027. \end{aligned}
Portanto o produto de 5 números (contando o 1 e os quatro primeiros primos 2,3,5,7) já é 210\le2027, mas se tentássemos ter 6 números diferentes e pairwise coprime (ou seja, k-1=6 fatores) o menor produto possível seria 2310>2027, o que viola a desigualdade do Passo 3. Assim não é possível ter k-1\ge 6. Concluímos que
k-1 \le 5 \quad\Rightarrow\quad k\le 6.
Portanto o tamanho máximo possível de X é no máximo 6.

Passo 5

Agora precisamos mostrar que isso é atingível: construir explicitamente um conjunto X\subset S com 6 elementos que satisfaça a propriedade. Vou construir uma sequência crescente a_1<\dots<a_6 que cumpre a_i\mid(a_j+1) para todo i<j.
Escolha:
\begin{aligned} a_1&=1, & c_1&=a_1+1=2,\\\ a_2&=2, & c_2&=a_2+1=3,\\\ a_3&=3, & c_3&=a_3+1=4,\\\ a_4&=5, & c_4&=a_4+1=6,\\\ a_5&=29,& c_5&=a_5+1=30,\\\ a_6&=869,& c_6&=a_6+1=870. \end{aligned}
Vou explicar como esses números foram escolhidos e verificar a propriedade.
Construção (intuição): escolho iterativamente c_{i+1}=a_{i+1}+1 como um múltiplo do MMC (ou do produto, já que os termos anteriores serão coprimos) dos a_1,\dots,a_i, e escolho o menor múltiplo que seja maior que c_i. Assim garanto que para todo j\le i vale a_j\mid c_{i+1}, isto é a_j\mid(a_{i+1}+1), que é exatamente a exigência para a_j<a_{i+1}.
Verificação passo a passo:
  • c_2=3 é múltiplo de a_1=1.
  • c_3=4 é múltiplo de \mathrm{lcm}(1,2)=2, logo 1\mid 4 e 2\mid 4.
  • c_4=6 é múltiplo de \mathrm{lcm}(1,2,3)=6, logo 1,2,3\mid 6.
  • c_5=30 é múltiplo de \mathrm{lcm}(1,2,3,5)=30, logo 1,2,3,5\mid 30.
  • c_6=870 é múltiplo de \mathrm{lcm}(1,2,3,5,29)=870, logo 1,2,3,5,29\mid 870.
Assim, para todo i<j temos a_i\mid c_j=a_j+1. Em palavras: cada elemento anterior divide todos os a_j+1 dos posteriores. Portanto a condição do enunciado é satisfeita por todos os pares ordenados i<j.
Também verifique que todos os a_i estão em S: a_6=869\le 2026, e os demais são bem menores; logo X=\{1,2,3,5,29,869\}\subseteq S.
Portanto existe X com 6 elementos que satisfaz a condição, então o limite k\le 6 do Passo 4 é atingido.

Passo 6

Resumo final do argumento (curtinho):
  • Mostramos que elementos de X são pairwise coprime.
  • Assim o produto dos k-1 menores elementos divide a_k+1\le 2027, dando a_1\cdots a_{k-1}\le 2027.
  • O menor produto possível para k-1 inteiros distintos coprimos (incluindo 1) excede 2027 já quando k-1\ge 6. Logo k\le 6.
  • Construímos explicitamente um conjunto de 6 elementos que funciona, então 6 é o máximo alcançável.

Resposta

6

Exercícios relacionados