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 \cdots \cup A_m$. We divide into the following different cases:

If $|U|=3$, then $m=1<|U|$. If $|U|=4$, then $m\le \left(\genfrac{}{}{0ex}{}{4}{3}\right)=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 \varnothing$. 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$