XXVIII-th Balkan Mathematical Olympiad

Notice first that a bad subset of $S$ contains at most one element from a good one, to deduce that a partition of $S$ into bad subset has at least as many members as a maximal good subset.

Notice further the elements of a good subset of $S$ must be among the terms of a geometric sequence whose ratio is a prime: if $x<y<z$ are elements of a good subset of $S$, then $y=x{p}^{\alpha }$ and $z=y{q}^{\beta }=x{p}^{\alpha }{q}^{\beta }$ for some primes $p$ and $q$ and some positive integers $\alpha$ and $\beta$, so $p=q$ for $z/x$ to be a power of a prime.

Next, let $P=\{2,3,5,7,11,\dots \}$ denote the set of all primes, let $$m=\max \{{\exp }_{p}x\mid x\in S\text{ and }p\in P\}$$ where ${\exp }_{p}x$ is the exponent of the prime $p$ in the canonical decomposition of $x$, and notice that a maximal good subset of $S$ must be of the form $\{a,ap,a{p}^2,\dots ,a{p}^m\}$ for some prime $p$ and some positive integer $m$ which is not divisible by $p$. Consequently, a maximal good subset of $S$ has $m+1$ elements, so a partition of $S$ into bad subsets has at least $m+1$ members.

Finally, notice by maximality of $m$ that the sets $$S_k=\{x\mid x\in S\text{ and }\sum _{p\in P}{\exp }_{p}x\equiv k(\mathrm{mod}m+1)\},k=0,1,2,\dots ,m.$$ form a partition of $S$ into $m+1$ bad subsets. The conclusion follows.