Assume students randomly choose their answers to a homework, with 15 questions, of 3 possible answers each. Which among these numbers is the smallest number of students so that with probability at least 0.5 at least two students give the same answers to all questions?
A) A number between 1 and 100
B) A number between 101 and 1000
C) A number between 1001 and 10000
D) A number between 10001 and 100000
I know that coll(q,N) >= q (q-1)/4N where q elements are chosen uniformly at random from a set of size N and that it is similar to the birthday paradox where N = {1, ... , 365} and 1 - 365 are each possible birthday, but I'm having trouble determining N is this case.