Let natural $n \ge 2$ be given. Let Laura be a student in a class of more than $n+2$ students, all of which participated in an olympiad and solved some problems. Additionally, it is known that: for every pair of students there is exactly one problem that was solved by both students; for every pair of problems there is exactly one student who solved both of them; one specific problem was solved by Laura and exactly $n$ other students. Determine the number of students in Laura's class.
Problem
Source: 2018 Latvia BW TST P8
Tags: combinatorics, combinatorics unsolved
06.06.2022 14:33
Please check the translation. It's impossible for all conditions to hold simultaneously. Let $A$ be the set of students who solve exactly one problem, and $B=A'$. Pick a pair of students in $A$, $\rightarrow$ all students in $A$ must solve the same problem, called $X$. Pick a pair of students in $A$ and $B$, $\rightarrow$ all students in $B$ must also solve $X$. Pick a pair of students in $B$ (we have $|B| \geq 2$), $\rightarrow$ apart from $X$, the problems solved by each one in $B$ are disjoint. Pick a pair of problems that are solved by $b_1,b_2 \in B$ (apart from $X$), $\rightarrow$ one student solves both of them, a contradiction.
07.06.2022 20:04
carefully wrote: Please check the translation. It's impossible for all conditions to hold simultaneously. Let $A$ be the set of students who solve exactly one problem, and $B=A'$. Pick a pair of students in $A$, $\rightarrow$ all students in $A$ must solve the same problem, called $X$. Pick a pair of students in $A$ and $B$, $\rightarrow$ all students in $B$ must also solve $X$. Pick a pair of students in $B$ (we have $|B| \geq 2$), $\rightarrow$ apart from $X$, the problems solved by each one in $B$ are disjoint. Pick a pair of problems that are solved by $b_1,b_2 \in B$ (apart from $X$), $\rightarrow$ one student solves both of them, a contradiction. Thank you for your consideration, the last constraint was indeed translated incorrectly. It is fixed now.
08.06.2022 21:18
This is equivalent to an existence of a combinatorial design. If there are no additional constraints, then there are multiple solutions to this, e.g. $q^2+q+1$, where $q$ is a power of prime. We only know that the number of students must be in the form $q^2+q+1$, but finding all satisfying $q$ is an open problem.