8. The set $S=\{1,2, \ldots, 2022\}$ is to be partitioned into $n$ disjoint subsets $S_{1}, S_{2}, \ldots, S_{n}$ such that for each $i \in\{1,2, \ldots, n\}$, exactly one of the following statements is true:
(a) For all $x, y \in S_{i}$ with $x \neq y, \operatorname{gcd}(x, y)>1$.
(b) For all $x, y \in S_{i}$ with $x \neq y, \operatorname{gcd}(x, y)=1$.
Find the smallest value of $n$ for which this is possible.
Solution. The answer is 15 .
Note that there are 14 primes at most $\sqrt{2022}$, starting with 2 and ending with 43 . Thus, the following partition works for 15 sets. Let $S_{1}=\{2,4, \ldots, 2022\}$, the multiples of 2 in $S$. Let $S_{2}=\{3,9,15 \ldots, 2019\}$, the remaining multiples of 3 in $S$ not in $S_{1}$. Let $S_{3}=\{5,25,35, \ldots, 2015\}$ the remaining multiples of 5 , and so on and so forth, until we get to $S_{14}=\{43,1849,2021\}$. $S_{15}$ consists of the remaining elements, i.e. 1 and those numbers with no prime factors at most 43 , i.e., the primes greater than 43 but less than 2022: $S_{15}=\{1,47,53,59, \ldots, 2017\}$. Each of $S_{1}, S_{2}, \ldots, S_{14}$ satisfies i., while $S_{15}$ satisfies ii.
We show now that no partition in 14 subsets is possible. Let a Type 1 subset of $S$ be a subset $S_{i}$ for which i. is true and there exists an integer $d>1$ for which $d$ divides every element of $S_{i}$. Let a Type 2 subset of $S$ be a subset $S_{i}$ for which ii. is true. Finally, let a Type 3 subset of $S$ be a subset $S_{i}$ for which i. is true that is not a Type 1 subset. An example of a Type 3 subset would be a set of the form $\{p q, q r, p r\}$ where $p, q, r$ are distinct primes.
Claim: Let $p_{1}=2, p_{2}=3, p_{3}=5, \ldots$ be the sequence of prime numbers, where $p_{k}$ is the $k$ th prime. Every optimal partition of the set $S(k):=\left\{1,2, \ldots, p_{k}^{2}\right\}$, i.e., a partition with the least possible number of subsets, has at least $k-1$ Type 1 subsets. In particular, every optimal partition of this set has $k+1$ subsets in total. To see how this follows, we look at two cases:
- If every prime $p \leq p_{k}$ has a corresponding Type 1 subset containing its multiples, then a similar partitioning to the above works: Take $S_{1}$ to $S_{k}$ as Type 1 subsets for each prime, and take $S_{k+1}$ to be everything left over. $S_{k+1}$ will never be empty, as it has 1 in it. While in fact it is known that, for example, by Bertrand's postulate there is always some prime between $p_{k}$ and $p_{k}^{2}$ so $S_{k+1}$ has at least two elements, there is no need to go this far-if there were no other primes you could just move 2 from $S_{1}$ into $S_{k+1}$, and if $k>1$ then $S_{1}$ will still have at least three elements remaining. And if $k=1$, there is no need to worry about this, because $21$ for all $x$ in the same set as $p$, then $\operatorname{gcd}(p, x)=p$, which implies that $p$ is in a Type 1 set with $d=p$. Similarly, if $\operatorname{gcd}\left(p^{2}, x\right)>1$ for all $x$ in the same set as $p^{2}$, then $p \mid \operatorname{gcd}\left(p^{2}, x\right)$ for all $x$, and so $p^{2}$ is in a Type 1 set with $d=p$ as well. Hence $p$ and $p^{2}$ must in fact be in Type 2 sets, and they cannot be in the same Type 2 set (as they share a common factor of $p>1$ ); this means that the optimal partition has at least $k+1$ subsets in total. A possible equality scenario for example is the sets $S_{1}=\left\{1,2,3,5, \ldots, p_{k}\right\}, S_{2}=\left\{4,9,25, \ldots, p_{k}^{2}\right\}$, and $S_{3}$ to $S_{k+1}$ Type 1 sets taking all remaining multiples of $2,3,5, \ldots, p_{k-1}$. This works, as $p_{k}$ and $p_{k}^{2}$ are the only multiples of $p_{k}$ in $S(k)$ with no prime factor other than $p_{k}$ and thus cannot be classified into some other Type 1 set.

To prove our claim: We proceed by induction on $k$. Trivially, this is true for $k=1$. Suppose now that any optimal partition of the set $S(k)$ has at least $k-1$ Type 1 subsets, and thus at least $k+1$ subsets in total. Consider now a partition of the set $S(k+1)$, and suppose that this partition would have at most $k+1$ subsets. From the above, there exist at least two primes $p, q$ with $p<q \leq p_{k+1}$ for which there are no Type 1 subsets. If $q<p_{k+1}$ we have a contradiction. Any such partition can be restricted to an optimal partition of $S(k)$ with $p<q \leq p_{k}$ having no corresponding Type 1 subsets. This contradicts our inductive hypothesis. On the other hand, suppose that $q=p_{k+1}$. Again restricting to $S(k)$ gives us an optimal partition of $S(k)$ with at most $k-1$ Type 1 sets; the inductive hypothesis tells us that this partition has in fact exactly $k-1$ Type 1 sets and two Type 2 sets from a previous argument establishing the consequence of the claim. However, consider now the element $p q$. This cannot belong in any Type 1 set, neither can it belong in the same Type 2 set as $p$ or $p^{2}$. Thus in addition to the given $k-1$ Type 1 sets and 2 Type 2 sets, we need an extra set to contain $p q$. Thus our partition of $S(k+1)$ in fact has at least $k-1+2+1=k+2$ subsets, and not $k+1$ subsets as we wanted. The claim is thus proved.
Returning to our original problem, since $p_{14}=43<\sqrt{2022}$, any partition of $S$ must restrict to a partition of $S(14)$, which we showed must have at least 15 sets. Thus, we can do no better than 15 .