Maths Olympiad Prep

Library / /284 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

Example 9 Let X=56|X|=56, for any 15 subsets of XX, if the union of any 7 of them contains at least nn elements, then among these 15 subsets, there must exist 3 subsets whose intersection is non-empty, find the minimum value of nn. (2006 China Mathematical Olympiad Problem)

A number or a short expression. Spacing and $ signs are ignored.

Solution

Solve nmin=41n_{\min }=41.
First, prove that n=41n=41 meets the conditions. Use proof by contradiction: Assume there exist 15 subsets of XX such that the union of any 7 of them contains at least 41 elements, and the intersection of any 3 of them is empty. Then each element belongs to at most 2 subsets. Without loss of generality, assume each element belongs to exactly 2 subsets (otherwise, add some elements to some subsets, and the conditions still hold). By the pigeonhole principle, there must be a subset, say AA, containing at least [56×215]+1=8\left[\frac{56 \times 2}{15}\right]+1=8 elements. Let the other 14 subsets be A1A_{1}, A2,,A14A_{2}, \cdots, A_{14}.

Consider any 7 subsets that do not include AA, each corresponding to 41 elements in XX. All 7-subset groups that do not include AA together correspond to at least 41C14741 C_{14}^{7} elements.

On the other hand, for an element aa, if aAa \notin A, then 2 of A1,A2,,A14A_{1}, A_{2}, \cdots, A_{14} contain aa, so aa is counted (C147C127)\left(C_{14}^{7}-C_{12}^{7}\right) times; if aAa \in A, then 1 of A1,A2,,A14A_{1}, A_{2}, \cdots, A_{14} contains aa, so aa is counted (C147C137)\left(C_{14}^{7}-C_{13}^{7}\right) times. Thus, 41C147(56A)(C147C127)+A(C147C137)=56(C147C127)A(C137C127)56(C147C127)8(C137C127)41 C_{14}^{7} \leqslant (56-|A|)\left(C_{14}^{7}-C_{12}^{7}\right) + |A| \cdot \left(C_{14}^{7}-C_{13}^{7}\right) = 56\left(C_{14}^{7}-C_{12}^{7}\right) - |A|\left(C_{13}^{7}-C_{12}^{7}\right) \leqslant 56\left(C_{14}^{7}-C_{12}^{7}\right) - 8\left(C_{13}^{7}-C_{12}^{7}\right), which simplifies to 48C127+8C13715C14748 C_{12}^{7} + 8 C_{13}^{7} \leqslant 15 C_{14}^{7}. Simplifying further, we get 3×48+4×1315×133 \times 48 + 4 \times 13 \leqslant 15 \times 13, or 196195196 \leqslant 195, which is a contradiction.

Next, prove that n41n \geqslant 41 using proof by contradiction.
Assume n40n \leqslant 40, and let X={1,2,,56}X=\{1,2, \cdots, 56\}. Define Ai={xXxi(mod7)}A_{i}=\{x \in X \mid x \equiv i(\bmod 7)\} (i=1,2,,7)(i=1,2, \cdots, 7) and Bj={xXxj(mod8)}B_{j}=\{x \in X \mid x \equiv j(\bmod 8)\} (j=1,2,,8)(j=1,2, \cdots, 8). Clearly, Ai=8|A_{i}|=8, AiAj=0|A_{i} \cap A_{j}|=0 for 1i<j71 \leqslant i<j \leqslant 7, Bj=7|B_{j}|=7, and BiBj=0|B_{i} \cap B_{j}|=0 for 1i<j81 \leqslant i<j \leqslant 8. Additionally, by the Chinese Remainder Theorem, AiBj=1|A_{i} \cap B_{j}|=1 for 1i71 \leqslant i \leqslant 7 and 1j81 \leqslant j \leqslant 8. Thus, for any 3 subsets, there must be 2 that are both AiA_{i} or both BjB_{j}, and their intersection is empty. For any 7 subsets, let there be tt (where 0t70 \leqslant t \leqslant 7) of them be AiA_{i} and 7t7-t be BjB_{j}. By the principle of inclusion-exclusion, the number of elements in the union of these 7 subsets is 8t+7(7t)t(7t)=49t(6t)4998t + 7(7-t) - t(7-t) = 49 - t(6-t) \geqslant 49 - 9 (since 0t70 \leqslant t \leqslant 7) =40= 40. Therefore, the union of any 7 subsets contains at least 40 elements, but the intersection of any 3 subsets is empty, so n41n \geqslant 41.

In conclusion, the minimum value of nn is 41.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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