Problem

Source: China TST 1996, problem 3

Tags: combinatorics unsolved, combinatorics



Let $ M = \lbrace 2, 3, 4, \ldots\, 1000 \rbrace$. Find the smallest $ n \in \mathbb{N}$ such that any $ n$-element subset of $ M$ contains 3 pairwise disjoint 4-element subsets $ S, T, U$ such that I. For any 2 elements in $ S$, the larger number is a multiple of the smaller number. The same applies for $ T$ and $ U$. II. For any $ s \in S$ and $ t \in T$, $ (s,t) = 1$. III. For any $ s \in S$ and $ u \in U$, $ (s,u) > 1$.