Problem

Source: Philippine MO 2022/8

Tags: number theory, combinatorics



The set $S = \{1, 2, \dots, 2022\}$ is to be partitioned into $n$ disjoint subsets $S_1, S_2, \dots, S_n$ such that for each $i \in \{1, 2, \dots, n\}$, exactly one of the following statements is true: (a) For all $x, y \in S_i$, with $x \neq y, \gcd(x, y) > 1.$ (b) For all $x, y \in S_i$, with $x \neq y, \gcd(x, y) = 1.$ Find the smallest value of $n$ for which this is possible.