Q3 Matemática  (Balkan MO 2011)

Seja $S$ um conjunto finito de inteiros positivos que tem a seguinte propriedade: se $x$ é membro de $S$, então todos os divisores positivos de $x$ também o são. Um subconjunto não vazio $T$ de $S$ é bom se sempre que $x,y\in T$ e $x<y$, a razão $y/x$ for uma potência de um número primo. Um subconjunto não vazio $T$ de $S$ é ruim se sempre que $x,y\in T$ e $x<y$, a razão $y/x$ não for uma potência de um número primo. Um conjunto de um elemento é considerado bom e ruim. Seja $k$ o maior tamanho possível de um bom subconjunto de $S$. Prove que $k$ também é o menor número de subconjuntos ruins disjuntos aos pares cuja união é $S$.