OBM 2017 - Nível 3 - P2

Problema 2

Seja $n \geq 3$ um inteiro. Prove que, para todo $k$ inteiro com $1 \leq k \leq \binom{n}{2}$, existe um conjunto $A$ com $n$ elementos inteiros positivos distintos tais que o conjunto $B = \{mdc(x, y) : x, y \in A, x\neq y\}$ (obtido a partir do máximo divisor comum de todos os pares de elementos distintos de $A$) contém exatamente $k$ elementos distintos.

Solução de Caio Hermano:

Vamos provar por indução em $k$ que conseguimos encontrar um conjunto $A$ satisfazendo as condições do enunciado para todo $1\leq k\leq \binom{n}{2}$.

Caso inicial: $k=1$: Considere o conjunto de $n$ primos distintos $A=\{p_1,p_2,...,p_n\}$. Note que $mdc(p_i,p_j)=1,\forall 1\leq i < j \leq n$ e, então, $A$ é uma solução para $k=1$.

Hipótese: Suponha que, para certo $1\leq k\leq \binom{n}{2}-1$, exista um conjunto $A=\{x_1,x_2,...,x_n\}$ para o qual $B = \{mdc(x, y) : x, y \in A, x\neq y\}$ contém exatamente $k$ elementos.

Passo indutivo: Vamos mostrar que existe um conjunto $A'$ para o qual $B' = \{mdc(x, y) : x, y \in A', x\neq y\}$ possua exatamente $k+1$ elementos.

Note que, pelo Princípio da Casa e dos Pombos, há dois pares $(i,j)\neq (k,l)$ de elementos em $A$ satisfazendo $mdc(x_i,x_j)=mdc(x_k,x_l)$. Tome um primo $P$ que não divide nenhum $x_i, 1\leq i \leq n$, e o conjunto $A'=A\setminus \{x_i,x_j\} \cup \{Px_i,Px_j\}$, ou seja, o conjunto $A$ tirando o par $\{x_i,x_j\}$ e acrescentando $\{Px_i,Px_j\}$.

Observe que, para $1\leq t\leq n, t\neq i,j$, temos: $mdc(Px_i,x_t)=mdc(x_i,x_t)$, $mdc(Px_j,x_t)=mdc(x_j,x_t)$ e $mdc(Px_i,Px_j)=Pmdc(x_i,x_j)\neq mdc(x_k,x_l)$. Portanto, $B' = \{mdc(x, y) : x, y \in A', x\neq y\}$ possui exatamente $k+1$ elementos (os mesmos que $A$ com adição do $Pmdc(x_i,x_j)$).

E o resultado segue por indução.