Maths Olympiad Prep

Library / /12 of 97

Combinatorics Difficulty 7.3 National olympiad, round 2 Find the answer

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.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

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 T T denote the number of triples (Si,Sj,Qk)(S_i, S_j, Q_k) such that students Si S_i and Sj S_j answered the same for question Qk Q_k .

First, consider the number of ways to choose 2 students out of 16, which is given by:
(162)=16×152=120. \binom{16}{2} = \frac{16 \times 15}{2} = 120.

Since any two students have at most one answer in common, we have:
T(162)=120. T \leq \binom{16}{2} = 120.

Next, let x,y,z,w x, y, z, w be the number of students choosing the first, second, third, and fourth options respectively for a given question, and let there be m m questions in total.

Applying the lemma and using the Cauchy-Schwarz inequality, we get:
(x2)+(y2)+(z2)+(w2)24. \binom{x}{2} + \binom{y}{2} + \binom{z}{2} + \binom{w}{2} \geq 24.

Thus, for m m questions, we have:
T24m. T \geq 24m.

Combining the inequalities, we get:
24m120    m5. 24m \leq 120 \implies m \leq 5.

Therefore, the maximum number of problems is:
[ 5 .\text{[ 5 .}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.