Olympiad Maths Prep

Library / /3 of 3

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Turkey

Find the largest real number tt such that, in any school with 20062006 students and 1414 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 tt.

Solution

t=2006/14t = 2006/14.
If every student is acquainted with every teacher, then all relevant ratios are 2006/142006/14. This means t2006/14t \le 2006/14. Now we will show that t2006/14t \ge 2006/14.
For 1i141 \le i \le 14, let aia_i denote the number of students who are acquainted with the ii\text{th} teacher, and for 1j20061 \le j \le 2006, let bjb_j denote the number of teachers who are acquainted with the jj\text{th} student. Let TT be the set of ordered pairs (i,j)(i, j) of teachers and students who are acquainted with each other. Observe that with this notation we have {j:(i,j)T}=ai0|\{j : (i, j) \in T\}| = a_i \ge 0 and {i:(i,j)T}=bj1|\{i : (i, j) \in T\}| = b_j \ge 1.
Assume that (io,jo)T(i_o, j_o) \in T satisfies the condition aio/bjoai/bja_{i_o}/b_{j_o} \ge a_i/b_j for all (i,j)T(i, j) \in T. Adding the inequalities aio/bjo1/ai1/bja_{i_o}/b_{j_o} \cdot 1/a_i \ge 1/b_j for all (i,j)T(i, j) \in T we obtain the inequality
aiobjo(i,j)T1ai(i,j)T1bj. \frac{a_{i_o}}{b_{j_o}} \sum_{(i,j) \in T} \frac{1}{a_i} \ge \sum_{(i,j) \in T} \frac{1}{b_j}.
Since
(i,j)T1ai=i=114{j:(i,j)T}1ai={i:ai0}aiai={i:ai0}114, \sum_{(i,j) \in T} \frac{1}{a_i} = \sum_{i=1}^{14} \sum_{\{j:(i,j) \in T\}} \frac{1}{a_i} = \sum_{\{i:a_i \ne 0\}} \frac{a_i}{a_i} = \sum_{\{i:a_i \ne 0\}} 1 \le 14,
and similarly,
(i,j)T1bj=j=12006{i:(i,j)T}1bj=j=12006bjbj=j=120061=2006, \sum_{(i,j) \in T} \frac{1}{b_j} = \sum_{j=1}^{2006} \sum_{\{i:(i,j) \in T\}} \frac{1}{b_j} = \sum_{j=1}^{2006} \frac{b_j}{b_j} = \sum_{j=1}^{2006} 1 = 2006,
we deduce that aio/bjo2006/14a_{i_o}/b_{j_o} \ge 2006/14, and hence t2006/14t \ge 2006/14.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.