Students have taken a test paper in each of $n \ge 3$ subjects. It is known that in any subject exactly three students got the best score, and for any two subjects exactly one student got the best scores in both subjects. Find the smallest $n$ for which the above conditions imply that exactly one student got the best score in each of the $n$ subjects.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
08.11.2010 01:58
In set terms we have $A_1,A_2,...,A_n$ with $|A_k|=3$ for all $k$ and $|A_i\cap A_j|=1$ for all $i\not = j$. Say $1$ is the element that appeared in the most number of sets. Wlog $1 \in \bigcap_{k=1}^m A_k$ with $m\ge 2$ and $1\not \in A_k$ for $k>m$. If the claim is not true then there exists some $j>m$. The sets $A_j\cap A_k\not = \{1\}$ for $k=1,2,..,m$ and therefore they must be distinct. But $|A_j|$ has only three elements so $m\le 3$. Now for all $j,k>m$ there are at most two sets such that $A_i\cap A_j = A_i \cap A_k$ else some element would be in more than three sets, contradicting the maximality of $1$. Since $|A_{1}\backslash \{1\}|=2$ there can be no more that $2\cdot 2=4$ sets $A_j$ with $j>m$. This means $n\le 7$ Equality: $(1,2,3),(1,4,5),(1,6,7),(2,4,6),(2,5,7),(3,4,7),(3,6,5)$ Therefore if there are $\ge 8$ subjects then one student must have recieved the top mark in all of them
29.10.2011 13:16
If there isn't a studeng solving all the problem,let a problem be A If it is solved by student a,b,c,let the set of problem solved by a is A1. Define A2,A3 similiarly. if two of the set A1,A2,A3 not only contains a,let them be A1,A2, If student a solve problem b,(diffrent from a),if$|A2|\ge\ 3$, and let problem b be solved by student d and e.Then at least two of the elements in the A2 is solved by the same student,it is a contradiction.so $|A2|\le\ 2$ and$|A1|\le\ 2$, $|A2|\le\ 2$,so $n\ge\ 7$