China Mathematical Olympiad

Suppose there exist 15 subsets of $X$, the union of every 7 of these 15 subsets contains at least 41 elements, and there exists no 3 of the 15 subsets whose intersection is nonempty. Since every element of $X$ can only belong 2 of the 15 subsets, we can suppose that every element of $X$ belongs to exactly 2 of the 15 subsets. Otherwise we can add a few more elements to some sets of the 15 subsets, and the condition still holds. By the Pigeonhole Principle, there is a set of the 15 subsets (suppose it is $A$), such that $|A|\ge \lfloor \frac{2\times 56}{15}\rfloor +1=8$. Let the other 14 sets be $A_1,A_2,\dots ,A_{14}$. The union of every 7 sets of $A_1,A_2,\dots ,A_{14}$ contains at least 41 elements. So the total number $y\le 41C_{14}^7$.

We use another way to compute the value of $y$. For $a\in X$, if $a\notin A$, then $a$ belongs to exactly 2 sets of $A_1,A_2,\dots ,A_{14}$. So $a$ is counted $C_{14}^7-C_{12}^7$ times. If $a\in A$, then $a$ belongs to only one set of $A_1,A_2,\dots ,A_{14}$. So $a$ is counted $C_{14}^7-C_{13}^7$ times. It follows that $$\begin{array}{r}41C_{14}^7\le y\le (56-|A|)(C_{14}^7-C_{12}^7)+|A|(C_{14}^7-C_{13}^7)\\ =56(C_{14}^7-C_{12}^7)-|A|(C_{13}^7-C_{12}^7)\\ \le 56(C_{14}^7-C_{12}^7)-8(C_{13}^7-C_{12}^7),\end{array}$$ that is, $196\le 195$, a contradiction.

Next, we prove $n\ge 41$. If $n\le 40$, suppose $X=\{1,2,\dots ,56\}$. let $$A_i=\{i,i+7,i+14,i+21,i+28,i+35,i+42,i+49\},$$ $$B_j=\{j,j+8,j+16,j+24,j+32,j+40,j+48\},$$ It is easy to see that $$\begin{array}{rlrl}|A_i|& =8(i=1,2,\dots ,7),& |A_i\cap A_j|& =0(1\le i<j\le 7),\\ |B_j|& =7(j=1,2,\dots ,8),& |B_i\cap B_j|& =0(1\le i<j\le 8),\\ |A_i\cap B_j|& =1(1\le i\le 7,1\le j\le 8).& & \end{array}$$ For every 3 of the 15 subsets, there are 2 sets both being $A_i$, or both being $B_j$. So the intersection of the 3 sets is empty. But for every 7 of the 15 subsets, for example, $$A_{i_1},A_{i_2},\dots ,A_{i_s},B_{j_1},B_{j_2},\dots ,B_{j_t}(s+t=7),$$ we have $$\begin{array}{rl}& |A_{i_1}\cup A_{i_2}\cup \cdots \cup A_{i_s}\cup B_{j_1}\cup B_{j_2}\cup \cdots \cup B_{j_t}|\\ & =|A_{i_1}|+|A_{i_2}|+\cdots +|A_{i_s}|+|B_{j_1}|+|B_{j_2}|+\cdots +|B_{j_t}|-st\end{array}$$ $$\begin{array}{rl}& =8s+7t-st=8s+7(7-s)-s(7-s)\\ & =(s-3{)}^2+40\ge 40.\end{array}$$ So $n\ge 41$.