There are 2019 students in a school, and some of these students are members of different student clubs. Each student club has an advisory board consisting of 12 students who are members of that particular club. An {\em advisory meeting} (for a particular club) can be realized only when each participant is a member of that club, and moreover, each of the 12 students forming the advisory board are present among the participants. It is known that each subset of at least 12 students in this school can realize an advisory meeting for exactly one student club. Determine all possible numbers of different student clubs with exactly 27 members.
Problem
Source: Turkey National Mathematical Olympiad, 2019
Tags: combinatorics, combinatorics unsolved, combinatorics proposed
25.12.2019 10:55
I can't understand, can you post the origin problem here?
25.12.2019 11:28
maybe we can change "each of the 12 students forming the advisory board" into "one of the 12 students forming the advisory board "?
25.12.2019 18:41
What do you mean by origin problem? It is in Turkish. No, I checked the Turkish version. Every one of 12 members of the board should be present so as to have a meeting.
26.12.2019 05:06
So, you mean 12 arbitrary students could form an advisory board of a club,is that true?
26.12.2019 18:49
Even the original of the problem is very confusing but I thought it was meant to say something like The students that are in any subset that has at least 12 students are able to make exactly 1 meeting.
30.12.2019 01:07
Here is a proof that there must be $\boxed{\binom{2003}{11}}$ student clubs with $27$ student clubs. Let there be $x_i$ clubs with $i$ students in them, for each $i \ge 12.$ Let's count the number of sets of $x+12$ students, for $x \in [0, 2007]$, which can conduct an advisory meeting in two different ways. On one hand, it is $\binom{2019}{x+12}$ from the condition of the problem. On the other hand, each student club with $i$ students contributes $\binom{i-12}{x}$ to this. Hence, we obtain that: $$\sum_{i = 12}^{2019} x_i \cdot \binom{i-12}{x} = \binom{2019}{x+12}, \forall 0 \le x \le 2007.$$ With this result, we are ready to prove by induction that $x_i = \binom{2030-i}{11}$ for all $12 \le i \le 2019,$ from which our claimed result follows. We will prove this by downwards induction on $i$. The base case $i = 2019$ is immediate by plugging $x = 2007$ into the above. To complete the inductive step, it suffices to show that: $$\sum_{i = t+12}^{2019} \binom{i-12}{t} \cdot \binom{2030-i}{11} = \binom{2019}{t+12}, \forall 0 \le t \le 2007$$ We will do this by a nice combinatorial argument. Consider the lattice paths from $(0, 0)$ to $(2007-t, t+12).$ Divide them into cases based on the $y-$value of the first time that they cross the line $x = t + \frac12.$ Double-counting finishes from here. The induction is now complete, and so we've shown that $x_{27} = \binom{2030-27}{11} = \boxed{\binom{2003}{11}}.$ $\square$