OBM 2015 - Nível 3 - P2

Problema 2

Seja $S=\{1,2,3,...,6n\}$, $n>1$. Encontre o maior valor de $k$ para o qual a seguinte afirmação é verdadeira: todo subconjunto $A$ de $S$ com $4n$ elementos tem pelo menos $k$ subconjuntos $\{a,b\}$ com $a<b$ e $b$ múltiplo de $a$.

Solução de Jonatan de Lima:

Inicialmente, com $A=\{2n+1,2n+2,...,6n\}$, vamos tentar contar os pares $\{a,b\}$. Se $a$ recebe um numero maior ou igual a $3n+1$, então $b\ge 6n+2>6n$, e não podemos formar par. Se $a$ recebe um número em $[2n+1,3n]$, então a única possibilidade é $b=2a$, pois $b\ge 3a\Rightarrow b\ge 6n+3>6n$, um absurdo. Logo, há $n$ pares e temos $k\le n$. Vamos mostrar que de fato tal cota é atingida para qualquer subconjunto $A$ e que portanto $k=n$.

Tome $A=\{a_1,a_2,...,a_{4n}\}$ com $a_1<a_2<\cdots<a_{4n}$. Escreva $a_j=2^{m_j}\cdot I_j$, onde $m_j\in \mathbb{Z_{\ge 0}}$ e  $I_j$ é um inteiro positivo ímpar. Veja que $I_j$ pode assumir apenas $3n$ valores, e pelo Princípio da Casa dos Pombos, como $|A|=4n$, há pelo menos $n$ pares $\{a_i,a_j\}$ com o mesmo $I$. E no caso de $a_i<a_j$ com $I_i=I_j$ temos $2^{m_i}\cdot I_i=a_i< a_j=2^{m_j}\cdot I_i\Rightarrow m_i<m_j$ e logo $a_i|a_j$, obtendo os $n$ pares requeridos.

Resposta: $k=n$.