MathDB

BP5

Part of 2020 China Northern MO

Problems(1)

Sets Whose Intersection Contains Relatively Prime Elements

Source: 2020 China North Mathematical Olympiad Basic level P5

8/4/2020
It is known that subsets A1,A2,⋯ ,AnA_1,A_2, \cdots , A_n of set I={1,2,⋯ ,101}I=\{1,2,\cdots ,101\} satisfy the following condition For any i,j (1≤i<j≤n), there exists a,b∈Ai∩Aj so that (a,b)=1\text{For any } i,j \text{ } (1 \leq i < j \leq n) \text{, there exists } a,b \in A_i \cap A_j \text{ so that } (a,b)=1 Determine the maximum positive integer nn.
*(a,b)(a,b) means gcd⁡(a,b)\gcd (a,b)
number theoryrelatively primecombinatoricsSets