AoPS - Problem

Source: VMO 2023 day 2 P6

Tags: set theory, combinatorics

a_507_bc

25.02.2023 09:45

There are $n \geq 2$ classes organized $m \geq 1$ extracurricular groups for students. Every class has students participating in at least one extracurricular group. Every extracurricular group has exactly $a$ classes that the students in this group participate in. For any two extracurricular groups, there are no more than $b$ classes with students participating in both groups simultaneously. a) Find $m$ when $n = 8, a = 4 , b = 1$ . b) Prove that $n \geq 20$ when $m = 6 , a = 10 , b = 4$. c) Find the minimum value of $n$ when $m = 20 , a = 4 , b = 1$.

$a)$ The answer is $\boxed{2}$. Claim: Assume the classes are $c_1,c_2,\ldots ,c_n$ and the extracurricular groups are $G_1,G_2,\ldots ,G_m$.Define $3{}$-tuple $(G_i,G_j,c_k)$,if class $c_k$ has student in both $G_i$ and $G_j$.Assume the number of such $3{}$-tuple is $N{}$. Obviously,we have $\sum_{i=1}^nc_i=am$.So $$N\leqslant C_m^2b\text{ and }N=\sum_{i=1}^nC_{c_i}^2\geqslant nC_{am/n}^2=\frac{am(\frac{am}{n}-1)}{2}$$ $b)$ Use the declaration above,we have $\frac{60}n\leqslant 3$.So $n\geqslant 20$. $c)$ The answer is $\boxed{14}$(Maybe).Same as above.