Set with a property This was a mock math olympiad problem sent to me by a friend.

Let $P$ be a set of prime numbers. Then, create a set $S$ of positive integers that satisfies the following property:

*

*For every element $p \in P$, $p$ is a factor of at least three elements in $S$.



Prove that for all sets $P$ and $S$, it is possible to divide $S$ into 4 nonempty subsets such that each $p$ is a factor of at least three integers.

I tried to consider the element $a \in P$ that was a factor of the least number of elements in $S$ and see what I could discover, but got nowhere. I also thought that perhaps some sort of algorithm would work too, but I didn't make any progress. Overall, I'm just not quite sure how to even start.
 A: Consider a partition $\{S_1,S_2,\ldots,S_k\}$ such that
($\ast$) each $p \in P$ has multiples in at least two different sets $S_i$
for which $k$ is as small as possible. (Note that there exist partitions for which ($\ast$) is true, such as the partition with only singletons, because of (1).) We intend to show that $k \le 3$.
Indeed, suppose that $k \ge 4$. By minimality of $k$, there exists a $p \in P$ that only divides numbers in $S_1$ and $S_2$; otherwise, we could merge $S_1$ and $S_2$ and ($\ast$) would still hold. Similarly, there is a $q \in P$ that only divides numbers in $S_3$ and $S_4$. But now $S$ does not contain a multiple of $pq$, contradicting (2).
A: Not entirely an answer, but too long to be a comment: note that primes and factoring here are a little bit of a red herring. It's possible to rewrite this question in such a way that they don't come into it at all. To see this, let the set of primes be labeled $\{p_1, p_2, \ldots, p_N\}$ (where possibly there is no last $N$, in which case we'll say that $N=\omega$ just for convenience). Then label each number $i\in S$ by the set $s_i$ of numbers $j$ such that $p_j$ is a factor of $S$. For instance, if $P$ is the set $\{2, 3, 11\}$ and $S$ is the set $\{12, 22, 99\}$, then we would have $p_1=2, p_2=3, p_3=11$ and $s_{12}=\{1,2\}$ since $p_1$ and $p_2$ are the factors of $12$; similarly $s_{22}=\{1,3\}$ and $s_{99}=\{2,3\}$. But now we can write the condition '$p_j$ divides $i$' as '$j$ is a member of $s_i$' and just write $S$ in terms of the $s_i$ (e.g., here $S$ would be $\left\{\{1,2\}, \{1,3\}, \{2,3\}\right\}$) and your initial properties become:

*

*for every $n \leq N$, there are at least two sets $s\in S$ such that $n\in s$

*for every $i, j\leq N$ there is at least one set $s\in S$ such that $i\in s$ and $j\in s$ (or equivalently, $\{i,j\}\subseteq s$)

And your result becomes that it's possible to divide $S$ into three sets $S_1, S_2, S_3$ such that for every $n\leq N$ at least two $S_i$ contain a set which has $n$ as an element.
