Maths Olympiad Prep

Library / /11 of 38

Combinatorics Difficulty 6.5 National olympiad Prove it China

Let XX be a set of 56 elements. Find the least positive integer nn such that for any 15 subsets of XX, if the union of every 7 sets of these subsets contains at least nn elements, then there exist 3 of the 15 subsets whose intersection is nonempty. (posed by Leng Gangsong)

Solution

Suppose there exist 15 subsets of XX, 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 XX can only belong 2 of the 15 subsets, we can suppose that every element of XX 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 AA), such that A2×5615+1=8|A| \ge \lfloor \frac{2 \times 56}{15} \rfloor + 1 = 8. Let the other 14 sets be A1,A2,,A14A_1, A_2, \dots, A_{14}.
The union of every 7 sets of A1,A2,,A14A_1, A_2, \dots, A_{14} contains at least 41 elements. So the total number y41C147y \le 41C_{14}^7.

We use another way to compute the value of yy.
For aXa \in X, if aAa \notin A, then aa belongs to exactly 2 sets of A1,A2,,A14A_1, A_2, \dots, A_{14}. So aa is counted C147C127C_{14}^7 - C_{12}^7 times. If aAa \in A, then aa belongs to only one set of A1,A2,,A14A_1, A_2, \dots, A_{14}. So aa is counted C147C137C_{14}^7 - C_{13}^7 times. It follows that
41C147y(56A)(C147C127)+A(C147C137)=56(C147C127)A(C137C127)56(C147C127)8(C137C127), \begin{aligned} 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{aligned}
that is, 196195196 \le 195, a contradiction.

Next, we prove n41n \ge 41.
If n40n \le 40, suppose X={1,2,,56}X = \{1, 2, \dots, 56\}. let
Ai={i,i+7,i+14,i+21,i+28,i+35,i+42,i+49}, A_i = \{i, i+7, i+14, i+21, i+28, i+35, i+42, i+49\},
Bj={j,j+8,j+16,j+24,j+32,j+40,j+48}, B_j = \{j, j+8, j+16, j+24, j+32, j+40, j+48\},
It is easy to see that
Ai=8(i=1,2,,7),AiAj=0(1i<j7),Bj=7(j=1,2,,8),BiBj=0(1i<j8),AiBj=1(1i7,1j8). \begin{aligned} |A_i| &= 8 \quad (i = 1, 2, \dots, 7), & |A_i \cap A_j| &= 0 \quad (1 \le i < j \le 7), \\ |B_j| &= 7 \quad (j = 1, 2, \dots, 8), & |B_i \cap B_j| &= 0 \quad (1 \le i < j \le 8), \\ |A_i \cap B_j| &= 1 \quad (1 \le i \le 7, 1 \le j \le 8). \end{aligned}
For every 3 of the 15 subsets, there are 2 sets both being AiA_i, or both being BjB_j. So the intersection of the 3 sets is empty.
But for every 7 of the 15 subsets, for example,
Ai1,Ai2,,Ais,Bj1,Bj2,,Bjt(s+t=7), A_{i_1}, A_{i_2}, \dots, A_{i_s}, B_{j_1}, B_{j_2}, \dots, B_{j_t} \quad (s+t=7),
we have
Ai1Ai2AisBj1Bj2Bjt=Ai1+Ai2++Ais+Bj1+Bj2++Bjtst \begin{aligned} & |A_{i_1} \cup A_{i_2} \cup \dots \cup A_{i_s} \cup B_{j_1} \cup B_{j_2} \cup \dots \cup B_{j_t}| \\ & = |A_{i_1}| + |A_{i_2}| + \dots + |A_{i_s}| + |B_{j_1}| + |B_{j_2}| + \dots + |B_{j_t}| - st \end{aligned}
=8s+7tst=8s+7(7s)s(7s)=(s3)2+4040. \begin{aligned} &= 8s + 7t - st = 8s + 7(7 - s) - s(7 - s) \\ &= (s - 3)^2 + 40 \ge 40. \end{aligned}
So n41n \ge 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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.