China Western Mathematical Olympiad

The set of positive integers satisfying the given condition consists of all positive multiples of $4$. We first prove that $n = 4k$ ($k \in \mathbb{Z}_+$) satisfies the condition. Define $A_1, A_2, \dots, A_{4k}$ as follows: $A_{4i-j} = \{4i-3, 4i-2, 4i-1, 4i\} \setminus \{4i-j\}$, for all $1 \le i \le k$ and $0 \le j \le 3$.

Second, we want to prove that if $4 \nmid n$, then such $n$ subsets do not exist. Suppose to the contrary that $A_1, \dots, A_n$ are different 3-element subsets fulfilling the condition stated in the problem. Let $A_1 = \{a, b, c\}$, consider all the given 3-element subsets with non-empty intersection; we may assume that they are $A_2, \dots, A_m$ after relabeling. Let $U = A_1 \cup A_2 \cup \dots \cup A_m$. We divide into the following different cases:

* If $|U| = 3$, then $m = 1 < |U|$.
* If $|U| = 4$, then $m \le \binom{4}{3} = 4 = |U|$.
* If $|U| \ge 5$, then we prove that $m < |U|$ as follows.

Suppose that $m \ge |U|$, then for any $2 \le i, j \le m$, we have $|A_1 \cap A_i| = 2$, $|A_1 \cap A_j| = 2$. As $|A_1| = 3$, we have $A_i \cap A_j \ne \emptyset$. And it follows from $|A_i \cap A_j| \ne 1$ that $|A_i \cap A_j| = 2$. It means that any two distinct subsets of $A_1, \dots, A_m$ have only two common elements.

Consider the four intersections $A_1 \cap A_2, A_1 \cap A_3, A_1 \cap A_4, A_1 \cap A_5$, it follows from the pigeon-hole principle that there are two intersections that are equal; by relabeling again, we may assume that they are $A_2 = \{a, b, d\}, A_3 = \{a, b, e\}$. Then for any $4 \le i \le m$, we have $a, b \in A_i$; otherwise, $A_i$ contains at least one of $a$ or $b$, and the other three elements $c, d$ and $e$, in this case, $|A_i| \ge 4$, which is impossible. Hence $|U| = m+2$, which contradicts $|U| = m$.

From the argument above, one can divide the subsets $A_1, \dots, A_n$ into several groups, and any two subsets in the same group have non-empty intersections. Moreover, the number of subsets in the same group is not more than the number of elements appearing in this group. As the number of subsets is $n$, which is equal to the number of elements in $\{1, 2, \dots, n\}$, so each group has exactly four subsets. It follows that $4|n$, which contradicts the original assumption $4 \nmid n$. $\square$