Browse · MathNet
Print15th Junior Turkish Mathematical Olympiad
Turkey counting and probability
Problem
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.
Solution
Suppose solved , but not where . Since is solved by exactly 4 students, and and are solved by exactly one student for each , there must be another student who solved two of the questions besides , a contradiction. Therefore . Since is solved by exactly four students, the number of questions cannot be more than .
On the other hand, an exam with 13 questions where is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by satisfies the conditions of the question.
On the other hand, an exam with 13 questions where is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by ; is solved by satisfies the conditions of the question.
Final answer
13
Techniques
Pigeonhole principleColoring schemes, extremal arguments