MathDB
GCD-related set partition

Source: Philippine MO 2022/8

March 19, 2022
number theorycombinatorics

Problem Statement

The set S={1,2,…,2022}S = \{1, 2, \dots, 2022\} is to be partitioned into nn disjoint subsets S1,S2,…,SnS_1, S_2, \dots, S_n such that for each i∈{1,2,…,n}i \in \{1, 2, \dots, n\}, exactly one of the following statements is true:
(a) For all x,y∈Six, y \in S_i, with x≠y,gcd⁡(x,y)>1.x \neq y, \gcd(x, y) > 1. (b) For all x,y∈Six, y \in S_i, with x≠y,gcd⁡(x,y)=1.x \neq y, \gcd(x, y) = 1.
Find the smallest value of nn for which this is possible.
Back to ProblemsView on AoPS