Professor recommending students problem 8 professors are recommending students. Assume that for any two professors there is exactly one common student recommended by them. Moreover, each student can be recommended by at most 3 professors.
How many students are there at least?
[I feel that clearly this can be reduced to a graph problem using for instance the incidence matrix, but I do not really have a concrete plan. Moreover, is there any systematic method for this type of questions? Many thanks.
what I tried is to test with some small examples, say for 4 professors, (trivially) 1 student is enough; for 5 professors it already gets messy, but it seems 5 students are needed. But I do not know how to generalize. In particular, I basically used brute force, and it is not clear to show that a certain number is the minimum number of the students.]
 A: Set up the standard incidence matrix, with columns as professors and rows as students. The entry is 1 if the professor recommends the student, and 0 otherwise.
We're after the minimum number of students. Let there be $s$ of them.
If there are students that are recommended by 0 or 1 professor, we can remove them from the list and reduce $s$ while not affecting the condition. Thus, in the optimal solution, there are no such students.
Let there be $a$ students recommended by 2 professors, and $b$ students recommended by 3 professors.
Let's count row pairs of 1-1.
By considering pairs of columns, the question states that there are exactly $ {8 \choose 2} = 28 $of them.
By considering each row, we have $ a \times 1 + b \times 3 $ of them.
Of course, not all solutions to $ a + 3b = 28$ will lead to a valid construction. EG We will shortly show that $(1,9)$ doesn't work.
Note that subject to $ a + 3b = 28$, we minimize $a+b$ by minimizing $a$ (or maximizing $b$).
Claim: Each student is recommended by at least 4 professors.
Proof: Suppose that student A is recommended by at most 3 professors. Then, there are at most $ 3 \times 2 $ other students who are jointly recommended. This means that there's at least 1 other student who isn't jointly recommended with student A, contradicting the condition.
Corollary:

*

*By counting the number of 1's, $2a + 3b \geq 8 \times 4$.

*$ a \geq 4 $

*$ s = a + b \geq 12$
Now, it remains to show that $ a = 4, b = 8$ is possible, giving the minimum $ s = 12$.
I have such an example, but will leave it to you to provide it.
This is essentially just trial and error, using the above as guidance.

 Note that we have equality throughout, so each professor recommends exactly 4 students.


 What can we say about the 4 students who are recommended by 2 professors?
 Those rows are likely a good candidate to start filling out the table.

