16 students took part in a competition. All problems were multiple choice style. Each problem had four choices. It was said that any two students had at most one answer in common, find the maximum number of problems.
Solution
Let 16 students take part in a competition where each problem is multiple choice with four choices. We are to find the maximum number of problems such that any two students have at most one answer in common.
Let denote the number of triples such that students and answered the same for question .
First, consider the number of ways to choose 2 students out of 16, which is given by:
Since any two students have at most one answer in common, we have:
Next, let be the number of students choosing the first, second, third, and fourth options respectively for a given question, and let there be questions in total.
Applying the lemma and using the Cauchy-Schwarz inequality, we get:
Thus, for questions, we have:
Combining the inequalities, we get:
Therefore, the maximum number of problems is: