Maths Olympiad Prep

Library / /6 of 8

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Vietnam

There are n2n \ge 2 classes organized m1m \ge 1 learning groups for students. Every class has students participating in at least one group. Every group has exactly aa classes that the students in this group participate in. For any two groups, there are no more than bb classes with students participating in both groups simultaneously.

a) Find mm when n=8,a=4,b=1n = 8, a = 4, b = 1.

b) Prove that n20n \ge 20 when m=6,a=10,b=4m = 6, a = 10, b = 4.

c) Find the minimum value of nn when m=20,a=4,b=1m = 20, a = 4, b = 1.

Solution

a) If m=1m = 1, then the class will have 8 group to attend, this is contradiction. If m3m \ge 3, consider any 3 groups X1,X2,X3X_1, X_2, X_3 then
nX1X2X3X1+X2+X3X1X2X2X3X1X34+4+4111=9, (contradiction). n \ge |X_1 \cup X_2 \cup X_3| \ge |X_1| + |X_2| + |X_3| - |X_1 \cap X_2| - |X_2 \cap X_3| - |X_1 \cap X_3| \ge 4 + 4 + 4 - 1 - 1 - 1 = 9, \text{ (contradiction).}
So m=2m = 2, we can take a simple case that each group has 4 participating classes and no class joins 2 groups.

b) Denote by SS the number of sets (A,{B,C})(A, \{B, C\}) in which class AA has students participating in groups BB and CC. There are (62)=15\binom{6}{2} = 15 pairs B,CB, C and any two groups have no more than 4 co-participating class so we have S154=60S \le 15 \cdot 4 = 60.
Let a1,a2,,ana_1, a_2, \dots, a_n be the number of groups that the student of class 1, 2, ..., nn participate to. There are 610=606 \cdot 10 = 60 in total of participants so a1+a2++an=60a_1 + a_2 + \dots + a_n = 60. We have
S=(a12)+(a22)+(a32)++(an2)=a1(a11)+a2(a21)++an(an1)2=12(a12+a22++an2)30. \begin{aligned} S &= \binom{a_1}{2} + \binom{a_2}{2} + \binom{a_3}{2} + \dots + \binom{a_n}{2} \\ &= \frac{a_1 \cdot (a_1 - 1) + a_2 \cdot (a_2 - 1) + \dots + a_n \cdot (a_n - 1)}{2} \\ &= \frac{1}{2}(a_1^2 + a_2^2 + \dots + a_n^2) - 30. \end{aligned}
Since S60S \le 60, we have
a12+a22++an22(60+30)=180. a_1^2 + a_2^2 + \dots + a_n^2 \le 2(60 + 30) = 180.
Applying the Cauchy-Schwarz inequality, we have
n(a12+a22++an2)(a1+a2++an)2=3600. n(a_1^2 + a_2^2 + \dots + a_n^2) \ge (a_1 + a_2 + \dots + a_n)^2 = 3600.
Hence 3600n180\frac{3600}{n} \le 180, which implies that n20n \ge 20.

c) There are a total of 204=8020 \cdot 4 = 80 participation so there will be a class DD with the number of student is at least 80n\lfloor \frac{80}{n} \rfloor. And the groups that class DD participates in will all have the same 1 co-participant class (class DD) and the remaining 3 classes of these groups are distinct. Therefore, we get
n380n+1380n+1    n2n2400. n \ge 3 \left\lfloor \frac{80}{n} \right\rfloor + 1 \ge 3 \cdot \frac{80}{n} + 1 \implies n^2 - n - 240 \ge 0.
This implies that n16n \ge 16. We can show a specific case with n=16n = 16 as following
A1={1,2,3,4},A2={1,5,6,7},A3={1,8,9,10},A4={1,11,12,13},A5={1,14,15,16},A6={2,4,9,13},A7={2,10,12,14},A8={2,6,8,16},A9={2,7,11,15},A10={3,5,12,16},A11={3,8,13,15},A12={3,6,10,11},A13={3,7,9,14},A14={4,5,10,15},A15={4,7,8,12},A16={4,9,11,16},A17={4,6,13,14},A18={5,8,11,14},A19={6,9,12,15},A20={7,10,13,16}. \begin{aligned} A_1 &= \{1, 2, 3, 4\}, \quad A_2 = \{1, 5, 6, 7\}, \quad A_3 = \{1, 8, 9, 10\}, \\ A_4 &= \{1, 11, 12, 13\}, \quad A_5 = \{1, 14, 15, 16\}, \quad A_6 = \{2, 4, 9, 13\}, \\ A_7 &= \{2, 10, 12, 14\}, \quad A_8 = \{2, 6, 8, 16\}, \quad A_9 = \{2, 7, 11, 15\}, \\ A_{10} &= \{3, 5, 12, 16\}, \quad A_{11} = \{3, 8, 13, 15\}, \quad A_{12} = \{3, 6, 10, 11\}, \\ A_{13} &= \{3, 7, 9, 14\}, \quad A_{14} = \{4, 5, 10, 15\}, \quad A_{15} = \{4, 7, 8, 12\}, \\ A_{16} &= \{4, 9, 11, 16\}, \quad A_{17} = \{4, 6, 13, 14\}, \quad A_{18} = \{5, 8, 11, 14\}, \\ A_{19} &= \{6, 9, 12, 15\}, \quad A_{20} = \{7, 10, 13, 16\}. \end{aligned}
So in this case, the minimum value of nn is 16. \square

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.