Quote: 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 student is allowed to NOT answer a question (leave it blank as an answer), right?

Quote: A student is allowed to NOT answer a question (leave it blank as an answer), right? No, the answer to every problem has only four choices, blank is not permitted.

Suppose there are $m$ problems $P_1,P_2...,P_m$ for problem $P_i$, suppose $a_i$ students answer first choice, $b_i$ secound choice, $c_i$ third choice and $d_i$ fourth choice. Since $a_i+b_i+c_i+d_i=16$ we have at least $4\binom{4}{2}=24$ pairs with an answer in common for each problem. Since there are $m$ problems there are at least $24m$ such pairs, but on the other hand there are at most $\binom{16}{2}=120$ such pairs. So we have that $m$ is at most $5$. Now can equality hold? since for $m=5$ we need stronger conditions (namely for every problem every choice is selected by 4 students, and every pair has a common choice for some problem) I think such construction is possible since i dont fin any other constraint.

I think I found an example \[ \begin{array}{|c|c|c|c|c|c|} \hline \text{student} & Q1 & Q2 & Q3 & Q4 & Q5 \\ \hline 1 & A & A & A & A & A \\ \hline 2 & A & B & B & B & B \\ \hline 3 & A & C & C & C & C \\ \hline 4 & A & D & D & D & D \\ \hline 5 & B & A & C & D & B \\ \hline 6 & B & C & A & B & D \\ \hline 7 & B & D & B & A & C \\ \hline 8 & B & B & D & C & A \\ \hline 9 & C & A & D & B & C \\ \hline 10 & C & D & A & C & B \\ \hline 11 & C & B & C & A & D \\ \hline 12 & C & C & B & D & A \\ \hline 13 & D & A & B & C & D \\ \hline 14 & D & B & A & D & C \\ \hline 15 & D & C & D & A & B \\ \hline 16 & D & D & C & B & A \\ \hline \end{array} \]

Here's a way to motivate my construction (which I did by trial-and-error back then). Consider the grid of 16 points $ \mathbb{Z}_{4}\times \mathbb{Z}_{4}$ (a finite affine plane). Consider all families of 4 parallel lines (each passing through 4 points). There are 5 such families, each corresponding to a unique slope. Each family of lines corresponds to one problem. For a given family, color the four lines with four different colors (corresponding to the 4 different multiple-choice answers). The 16 points correspond to the 16 questions. This gives the desired construction.

Oops, I meant $ \mathbb{F}_{4}\times \mathbb{F}_{4}$, where $ \mathbb{F}_{4}$ is the field with 4 elements.

Sorry, but I don't quite understand what you mean. Would it be possible to draw a diagram?

@ Pascual: I have another way to prove that there cant be more than 5 questions. Suppose the Q1(question 1) was answered as option 'a' by p1 (participant 1),p2,p3 and p4 .(only: There cant be a p5 as all of them (p1 to p5) have to opt for different options of Q2 and it would not be possible by pigeon hole principle). So 1 can have common options with {2,3,4}{5,6,7}{8,9,10}{11,12,13}{14,15,16} Hence not more than 5 questions. But we need a construction to say this is surely possible and billzhao does it(I have not checked it but). @billzhao: I only get the feel of your 4*4 affine plane construct, but not able to get the complete proof. Would you explain in detail? I feel this problem somehow connects with Kirkman schoolgirls problem, any idea? You created a example, can we enumerate the number of such possible constructs?

A more clear solution (indicating double-counting) is as follows. Suppose, there are $m$ tasks in the contest. Count the total number of triples of form $(C_i,C_j,Q_k)$, where contestants $1\leq i <j\leq 16$ agreed on problem $k\in\{1,2,\dots,m\}$. From the perspective of each pair, there is at most one such triple, hence, the number is upper bounded by $\binom{16}{2}$. Now, from the perspective of any problem, if $x,y,z,t,$ are the number of people selected first choice, ..., fourth choice, then there is precisely $\binom{x}{2}+\binom{y}{2}+\binom{z}{2}+\binom{t}{2}$ pairs, agreed on problem $k$. Using convexity of Binomial coefficients with Jensen's inequality, and the fact that $x+y+z+t=16$, the total number of contestants, we get, $\binom{x}{2}+\binom{y}{2}+\binom{z}{2}+\binom{t}{2}\geq 24$. This yields, $\binom{16}{2}\geq 24m$, namely, $m\leq 5$. An example of $m=5$ is easy to construct, and is provided above.

A very much similar solution to the one above.

Let the students be $S_1, S_2, \ldots, S_{16}$ and the questions be $Q_1, Q_2, \ldots, Q_n$. Define $X$ as the number of triples $(S_i, S_j, Q_k)$ where $1 \le i < j \le 16$ such that $S_i$ and $S_j$ got the same answer for $Q_k$. Because any two students have at most one answer in common, we have $$X \le 1 \cdot \binom{16}{2} = 120.$$Now, we find a lower bound for $X$ by analyzing each question individually. WLOG, pick $Q_1$. For $Q_1$, suppose $a$ people answered "A", $b$ people answered "B", $c$ people answered "C", and $d$ people answered "D". Since $a+b+c+d = 16$, Cauchy-Schwarz implies $$\binom{a}{2} + \binom{b}{2} + \binom{c}{2} + \binom{d}{2} = \frac{a^2 + b^2 + c^2 + d^2 - (a+b+c+d)}{2}$$$$\ge \frac{(a+b+c+d)^2}{8} - 8 = 24.$$Thus, there are at least $24$ triples of the form $(S_i, S_j, Q_1)$. Now, symmetry implies $$24n \le X \le 120 \implies n \le 5$$as required. $\blacksquare$ Remarks: Also see here and here.

Consider the triplets \( (\text{student}, \text{student}, \text{common answer}) \). We see that fixing the students, there are at most \( \binom{16}{2} \) such triplets. See question 1 and each option. Let \( a \) be the number of students who pick the first option, \( b \) the number who pick the second option, \( c \) the number who pick the third option, and \( d \) the number who pick the fourth option (note \( a + b + c + d = 16 \)). Thus, the number of such triplets is given by: \[ \binom{a}{2} + \binom{b}{2} + \binom{c}{2} + \binom{d}{2} = \frac{a^2 + b^2 + c^2 + d^2 - 16}{2} \]For the first question, since \( a^2 + b^2 + c^2 + d^2 \geq 64 \) by the Cauchy-Schwarz inequality, we have at least \( 24 \) such triplets. Repeating this for the other questions, there are at least \( 24 \cdot q \) such triplets (where \( q \) denotes the number of questions). Therefore, \[ 24q \leq \binom{16}{2} \implies q \leq 5. \]We see that there is a construction for $q = 5$ (mentioned above, not putting it here since it would take too much time to latex), so our answer is $\boxed{5}$

Ooo nice problem For the bound, notice that every question creates atleast $4\cdot \binom 42=24$ common answers due to jensen, and since the maximum number of pairs of possible common answers is $\binom{16}2=120$, we get a bound of $\frac{120}{24}=5$, as desired. Make the students to be elements in $\mathbb{Z}_4\times \mathbb{Z}_4$ in the plane and each question corresponds to the 5 family of parallel lines, each of which contains 4 lines which correspond to a certain option in the question, and each student chose the option from their respective family such that it lies on the line of that family. Its not so hard to see that this works

Same as everything above, died on the construction though. I don't get the finite field approach above, is there any better method?