Denote $A_i \; (1 \le i \le 25)$ be the set of students that like $i$th jury and $|A_i|=a_i$. a) We have $\sum_{i=1}^{25}a_i =10\cdot 100$. This follows there exists $a_i \ge 40$, wlog $a_{25}$. We exclude $40$ students that like $25$-th jury to get $60$ students and $24$ juries left. If we denote $b_i \; (1 \le i \le 24)$ be the number of students among $60$ students that like $i$-th jury then $\sum_{i=1}^{24}b_i=10 \cdot 60$. This follows there exists $b_i \ge 25$. We exclude these $25$ students to get $35$ students and $23$ juries. By doing the same thing, we can reach to $7$ juries that know all the students. b) WLOG, assume that $a_1 \le a_2 \le \cdots \le a_{25}$. We start from $1$st jury to $25$th jury, each time pick $10$ students that like that jury, and must follow the following greedy algorithm: If after we pick $10$ students from $A_i$, there still $k \le A_i-10$ students (that like $i$-th jury) left that haven't been picked. We put these students into a set $S$ in order, the latest students at the left. For example, $S= \{ G_1,G_2, \cdots , ... , G_{25} \}$ where $G_i$ is the left over students after picking $10$ from $a_i$ in $i$th jury. After we pick, we exclude the jury and the students being picked (take them out from all the sets $A_i$). After excluding juries and students, we rearrange the $A_i$ and pick all the juries so $|A_j| \le 10$. This will lead to either we prove the statement or the juries left all have $|A_j| \ge 11$. After finishing picking $A_{i}$, we move to pick students that like $i+1$th jury in $A_{i+1}$, but our priority is to pick as much students in $A_{i+1} \cap S$ as possible, and if there is still $h \le 10$ more students need to pick, then we pick arbitrary from $A_{i+1} \setminus S$. Remember to pick $A_{i+1} \cap S$ in order from oldest to latest (which means from $G_1$ to $G_{25}$). Now, we need to guarantee that with this, we can always make every students be checked by the jury he/she likes. The worst case scenario is that at some point, there will be a student $X$ remaining that doesn't like any jury remaining. If that happens, consider $10$ juries that $X$ likes, denote their set to be $B_i \; (1 \le i \le 10)$ with $|B_i|=b_i$ and $b_1 \le b_2 \le \cdots \le b_{10}$. This means $10<b_i$ (otherwise $X$ will be picked by some $i$th jury with $b_i \le 10$). Condition 2 of the algorithm guarantees that we can always bring back to a situation that all the juries have $|B_i| \ge 11$. Next, after jury with $B_1$ picks students, then student $X$ must be left out so $X$ is in $S$. After jury with $B_2$ picks students, since out priority is $B_2 \cap S$, so there must be exactly $10$ students + student $X$ who like jury $B_2$ in $S$ (from condition 2 and optimal picking of $B_2 \cap S$ in condition 3). After picking $B_2$, those $10$ students that like $B_2$ will be picked, hence similarly, there will be $10$ more students in $S$ that like jury $B_3$. If there is no jury $A_j$ between $B_i,B_{i+1}$ (means $|B_i| \le |A_j| \le |B_{i+1}|$) then this will continue until jury with $B_{10}$ and we find that $|S| \ge 10\cdot 9+1=91$ at stage after picking students for jury $B_1$. This is obviously a contradiction since $|B_1| \ge 11$ so that means after picking $10$ students that likes jury $B_1$, we must have $|S| \le 90$. If there is a jury $A_j$ between some $B_i,B_{i+1}$ then from the oldest to latest rule in condition 3, we find that this won't affect that $|S| \ge 91$ at stage picking $10$ from $B_1$ (otherwise, if there is no $10$ students that like $B_{i+1}$ in $S$ at stage after picking $10$ from $B_1$, according to oldest, latest rule, we must pick student $X$ who like $B_{i+1}$ because $X$ is in older group). Thus, the scenario that student $X$ can't find jury he/she like cannot happen. In other words, this algorithm works. $\square$ Comment. For a) by using Probabilistic method, we can guarantee picking $8$ juries so each student likes at least one jury. Indeed, pick $8$ juries randomly, the probability that a student doesn't like all $8$ juries is $\frac{\binom{15}{8}}{\binom{25}{8}}$. Hence, if $X$ be the number of students that don't like all $8$ juries, according to Linearity of Expected value, we have $\mathbb{E}[X]= 100 \cdot \frac{\binom{15}{8}}{\binom{25}{8}}<1$. Thus, there exists way to pick $8$ juries so $\mathbb{E}[X]=0$, or no students that don't like all $8$ juries. I don't think probabilistic method can't prove for $7$ juries because $100 \cdot \frac{\binom{15}{7}}{\binom{25}{7}} >1$. I hope someone can solve b) using probabilistic method, I've tried but fail. ___________________________________________________________ Could someone please check the solution for b) ? Thanks.

VN TST 2015

Just a comment: it's not probabilistic method, but hall's lemma kills part b)

The strategy for part b is quite simple. Suppose we have already chosen appropriate juries for the first $k$ students. If $k = 100$, then we are done. For $k < 100$, take one of the rest students and consider the 10 juries, who this student likes. Among these, there is at least one who has been chosen by no more than $[k/10] \le 9$ times. Now we can pair up this student and jury pair $\blacksquare$.

@godfjock could you tell the hall's lemma solution?