Maths Olympiad Prep

Track / Stage 5 / 246 of 400 #846 of 1964

Problem 846

AIME late
Combinatorics Difficulty 5.6 Find the answer

For example, 811 sets M1,M2,,M11M_{1}, M_{2}, \cdots, M_{11}, each set has 5 elements, and the intersection of any two sets is non-empty. Find the minimum possible value of the maximum number of sets that have a common element.
(1994 Romanian National Team Selection Test)

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

Let n(x)n(x) denote the number of sets containing the element xx. Let TT be the set of all elements in the 11 sets M1,M2,,M11M_{1}, M_{2}, \cdots, M_{11}, i.e., T=i=111MiT=\bigcup_{i=1}^{11} M_{i}.
From the problem, we know that xTn(x)=511=55\sum_{x \in T} n(x)=5 \cdot 11=55.
Let Cn(x)2C_{n(x)}^{2} denote the number of ways to choose two sets from n(x)n(x) sets, which is also the number of ways to choose two sets containing the element xx from the 11 sets (if n(x)=1n(x)=1, we define Cn(x)2=0C_{n(x)}^{2}=0). Since the intersection of any two sets Mi,Mj(1i<j11)M_{i}, M_{j}(1 \leqslant i<j \leqslant 11) is non-empty, there is at least one common element xTx \in T between MiM_{i} and MjM_{j}. In other words, for any pair of sets (Mi,Mj)(1i<j11)\left(M_{i}, M_{j}\right)(1 \leqslant i<j \leqslant 11), there is at least one common element xTx \in T. The pair (Mi,Mj)\left(M_{i}, M_{j}\right) is a pair of sets chosen from the n(x)n(x) sets containing xx, so we have
xTCn(x)2C112=55\sum_{x \in T} C_{n(x)}^{2} \geqslant C_{11}^{2}=55, i.e., 12xTn(x)[n(x)1]55\frac{1}{2} \sum_{x \in T} n(x)[n(x)-1] \geqslant 55.
Let n=max{n(x)xT}n=\max \{n(x) \mid x \in T\}, then from the above inequality, we get 12(n1)xTn(x)55\frac{1}{2}(n-1) \sum_{x \in T} n(x) \geqslant 55.
Using ()(*), we get 12(n1)1\frac{1}{2}(n-1) \geqslant 1, thus n3n \geqslant 3.
If n=3n=3, then for any xTx \in T, we have n(x)3n(x) \leqslant 3. We will prove that there does not exist xTx \in T such that n(x)2n(x) \leqslant 2.

By contradiction. If there exists some xTx \in T such that n(x)2n(x) \leqslant 2, then at least 112=911-2=9 sets do not contain xx. Without loss of generality, assume M3,M4,,M11M_{3}, M_{4}, \cdots, M_{11} do not contain xx, and M1M_{1} contains xx. Since each of M3,M4,,M11M_{3}, M_{4}, \cdots, M_{11} has at least one common element with M1M_{1}, and this common element is not xx, it must be one of the other 4 elements in M1M_{1}. These 4 elements belong to M3,M4,,M11M_{3}, M_{4}, \cdots, M_{11}, which are 9 sets, so there must be an element yy that belongs to at least three of these 9 sets. Adding yM1y \in M_{1}, we have n(y)4n(y) \geqslant 4. This contradicts n=3n=3.

Therefore, when n=3n=3, for any xTx \in T, we have n(x)=3n(x)=3. Thus, we have 3T=1153 \cdot|T|=11 \cdot 5, which gives T=553|T|=\frac{55}{3}, a contradiction.
Hence, we get n4n \geqslant 4.
When n=4n=4, we can provide an example that meets the conditions of the problem as follows:
M1=M2={1,2,3,4,5},M3={1,6,7,8,9},M4={1,10,11,12,13},M5={2,6,9,10,14},M6={3,7,11,14,15},M7={4,8,9,12,15},M8={5,9,13,14,15},M9={4,5,6,11,14},M10={2,7,11,12,13},M11={3,6,8,10,13}. \begin{array}{l} M_{1}=M_{2}=\{1,2,3,4,5\}, M_{3}=\{1,6,7,8,9\}, \\ M_{4}=\{1,10,11,12,13\}, M_{5}=\{2,6,9,10,14\}, \\ M_{6}=\{3,7,11,14,15\}, M_{7}=\{4,8,9,12,15\}, \\ M_{8}=\{5,9,13,14,15\}, M_{9}=\{4,5,6,11,14\}, \\ M_{10}=\{2,7,11,12,13\}, M_{11}=\{3,6,8,10,13\} . \end{array}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.