Skip to main content
OlympiadHQ

Browse · MathNet

Print

14th Turkish Mathematical Olympiad

Turkey counting and probability

Problem

Find the largest real number such that, in any school with students and teachers where every student is acquainted with at least one teacher, a student and a teacher can be found such that they are acquainted with each other, and the ratio of the number of students who are acquainted with the teacher to the number of teachers who are acquainted with the student is at least .
Solution
. If every student is acquainted with every teacher, then all relevant ratios are . This means . Now we will show that . For , let denote the number of students who are acquainted with the \text{th} teacher, and for , let denote the number of teachers who are acquainted with the \text{th} student. Let be the set of ordered pairs of teachers and students who are acquainted with each other. Observe that with this notation we have and . Assume that satisfies the condition for all . Adding the inequalities for all we obtain the inequality Since and similarly, we deduce that , and hence .
Final answer
2006/14

Techniques

Counting two waysColoring schemes, extremal arguments