Grace marks.

In a college, each student can give grace mark to another student (at max to 3 students). However there cannot be a mutual exchange, i.e. if A gives to B then he cannot receive back from B. Find the minimum number of students (n) that must be present for every student to achieve maximum grace marks and also find the number of ways that this can be achieved for n.




Approach:
min # of students should be 7 (let, A,B,C,D,E,F,G), as a student A can give grace marks to 3 students (let, B,C,D), 
and can get max grace marks (which is 3) from rest 7 - 3 (B,C,D can't give grace to A) - 1 (A itself) = 3 (i.e. E,F,G).


Ok, so n = 7 ist Let's see why any less than 7 would not work. Depict the mark-giving activity with a directed graph where the students are nodes and x giving y a grace mark is represented by a directed edge from x to y. Then the number of directed edges for n students is 3n (because everyone must receive 3). Each directed edge of course involves a pair of students, and the number of such pairs is (n choose 2) = n(n-1)/2. Now if 3n > n(n-1)/2, then by the Pigeonhole Principle some pair of students must share two or more directed edges. Since a student can't give another student more than mark, they must be giving each other marks (forbidden). 


Hence we must have 3n <= n(n-1)/2, i.e., n >= 7.


Another way to look at it is:
if a student can give grace to k other students, there remaining (n-k-1) students who could give grace points to him. 
To get min value of n, equating k = n-k-1, we get n = 2k+1. 


For n = 7, # of ways seems to be 6c3 * 5c3 * 4c3.