In an exam every question is solved by exactly four students, every pair of questions is solved by exactly one student, and none of the students solved all of the questions. Find the maximum possible number of questions in this exam.
Problem
Source: Junior Turkish Mathematical Olympiad 2010 Problem 3
Tags: combinatorics proposed, combinatorics, Set systems, Projective plane
mavropnevma
24.07.2011 17:53
The finite projective plane of order $3$, having $3^2 + 3 + 1 = 13$ points and $13$ lines, each line containing $3+1=4$ points and through each point passing $4$ lines (with any two distinct lines obviously meeting in exactly one point).
IstekOlympiadTeam
06.04.2015 18:54
mavropnevma wrote: The finite projective plane of order $3$, having $3^2 + 3 + 1 = 13$ points and $13$ lines, each line containing $3+1=4$ points and through each point passing $4$ lines (with any two distinct lines obviously meeting in exactly one point). What is the answer
mavropnevma
06.04.2015 23:20
Well, $13$; isn't that clear from that post?
IstekOlympiadTeam
08.04.2015 16:04
mavropnevma wrote: Well, $13$; isn't that clear from that post? I think not
lckihi
02.12.2018 18:11
How to prove that 13 is the maximum? Thanks. My attempt:
Firstly, we show that a student can solve at most $4$ questions. Suppose student $s$ solved $5$ questions denoted by $q_i, i=1$ to $5$. Exactly $3$ more students other than $s$ solve each $q_i$. Given $s$ didn't solve every question, these exist a question $q_6$ that $s$ didn't solve. There are $5$ pairs of questions $(q_6, q_i)$ but $q_6$ is solved by exactly $4$ students, so there is a pair of questions not solved by any student. A contradiction.
Then, we show that there are at most $13$ questions. Suppose $q$ is a question. It is solved by exactly
$4$ students denoted by $s_i, i=1$ to $4$. Note that $q$ is the only common question solved by $s_1$ to $s_4$, otherwise there will be a pair of questions solved by more than one student. If $p$ is a question other than $q$, then $p$ is also solved by someone from $s_1$ to $s_4$, otherwise no student will solve the pair of questions $(q, p)$. Since $s_i$ can solve at most $4$ questions, he solves at most $3$ more problems other than $q$. Hence, the maximum number of problems is $3\times 4+1=13$.
Example for 13: https://en.wikipedia.org/wiki/Projective_plane
XbenX
02.12.2018 21:50
I'll post my solution because it is a little bit different . Assume that there exist a student that solved $5$ questions call it $a_1$ , if the other question is not solved by this student then it is solved by $5$ other students , contradiction since a question is solved by $4$ students , so other questions also are solved by $a_1$ , again contradiction because $a_1$ can't solve all questions ,so at most a student can solve $ 4$ questions . Let $a_1,a_2,a_3,a_4$ be the solvers of a question , call it $ Q1$ ,at most $a_1, a_2,a_3, a_4$ solved $16$ question and since $Q_1$ here is counted $ 4$ times , we have that maximum of questions is $16-3=13$ .