At a summer school there are $7$ courses. Each participant was a student in at least one course, and each course was taken by exactly $40$ students. It is known that for each $2$ courses there were at most $9$ students who took them both. Prove that at least $120$ students participated at this summer school.
Problem
Source: 2017 Moldova TST, Day 2, Problem 4
Tags: combinatorics
19.03.2017 17:57
Let $n$ be the number of students, $C_1,C_2,\dots, C_7$ be that $7$ courses.Suppose that $n\le119$. And let $a_i$ be the number of courses that $i^{th}$ student participate. We get that $\sum_{i=1}^{n}a_i=7\times40=280$. Then consider the number of $\left(S,C_i,C_j\right)$ for which student $S$ participate in $C_i,C_j$, called $X$. So $X=\sum_{i=1}^{n}{a_i\choose2}$. But from $n\le119$ and $\sum_{i=1}^{n}a_i=280$, we get that $X\ge77{2\choose2}+42{3\choose2}=203$. But $X\le9{7\choose2}=189$. Contradiction. So $n\ge120$.
19.03.2017 17:58
Let $n$ be the number of students. Define an incidence matrix with $n$ rows and $7$ coloumns, such that $$a_{i,j}=\begin{cases}1 \quad\text{if student $i$ participates in course $j$} \\ 0 \quad \text{otherwise}\end{cases}.$$Counting by coloumns, we know that the sum of the entries is $280$. Let $s_i$ be the sum of the $i$th row. Thus, $$\sum_{i=0}^n s_i=280.$$Now, we have to deal with the second condition. Obviously, there are $\sum_{i=0}^n \binom{s_i}{2}$ ways to choose two entries $a_{i,j}, a_{i,k}$ such that $a_{i,j}=a_{i,k}=1$. On the other hand, this sum is at most $9\cdot \binom{7}{2}$. Hence, $$\frac{1}{2}\sum_{i=0}^n s_i^2-s_i \leqslant 189 \Rightarrow \sum_{i=0}^n s_i^2 \leqslant 658.$$However, by Jensen or AM-GM $$\sum_{i=0}^n s_i^2 \geqslant \frac{1}{n}\left(\sum_{i=0}^n s_i\right)^2 = \frac{280^2}{n}.$$Combining these two results one gets $$\frac{280^2}{n} \leqslant 658 \Rightarrow n\geqslant 120.$$ EDIT: sniped
19.03.2017 18:05
Alternatively let there be $n$ students, and let student $i$ participate in $s_i$ classes. We have $\sum_{i=1}^n s_i=280$ and that $\tfrac{1}{\tbinom{7}{2}}\sum_{i=1}^n \tbinom{s_i}{2}\leq 9$. By convexity then we must have $\tbinom{\tfrac{280}{n}}{2}\leq 9\cdot \tbinom{7}{2}$, and it is a well-known fact that $\tfrac{280\cdot 140}{9\cdot 21+140}>119$, so we conclude $\Box$
19.03.2017 18:46
What kind of TST is that? Thnxs in advance..
19.03.2017 18:47
EfthymiosN wrote: What kind of TST is that? Thnxs in advance.. It is IMO/BMO TST