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.
Problem
Source: Philippine MO 2022/8
Tags: number theory, combinatorics
29.03.2022 21:54
Since there is no solution still, I will post sketch of my solution. I hope I didn't make any mistake. The answer is $14$. To construct $S_i$s, let's first construct $S'_i$s. Let $p_i$ be $i$th prime number. $S'_i$ be set of numbers that are less than $2023$ and divisible by $p_i$, for $i=1,2,...,12$. $S'_{13}=\{41\cdot 43,43\cdot 47,41\cdot 47\}$. $S'_{14}$ is set of all prime powers less than $2023$ $($ including $1$st power, I mean $p,p^2,...,p^r)$ and $1$. Then take any number lies in $[1,2022]$ and remove it from all sets that it's in, except $1$ of them, so each number will be at most $1$ set. After this prosses we will get $S_i$ from $S'_i$. Also since $41\cdot 53>2022$ we get all numbers are placed in exactly $1$ of the sets. It's obvious that all sets holds $1$ of statements, so we are done with construction. Main part of the problem is to prove $13$ is not valid. Using induction we can show that if we divide set $T_{n}=\{1,p_1\cdot p_2,p_1\cdot p_3,...,p_1\cdot p_{n},p_2\cdot p_3,...,p_2\cdot p_{n},...,p_{n-1}\cdot p_{n}\}$ into disjoint sets such that all sets holds exaclty $1$ of given statements, then we need at least $n-1$ sets. Observe that $T_{15}\subseteq S \implies n\geq 14$. So we are done!
18.01.2023 07:04
$S_{14}'$ seems to have $1, 43$ and $43^2$, which are not in any of the lower $S_i'$, so $S_{14}$ fails the condition: ie $gcd(1,43)=1$ and $gcd(43,43^2)=43$. The official solutions doesn't seem to have a complete proof either, I can sketch one at some point if there is enough interest for me to bother.