Maths Olympiad Prep

Library / Turkish Mathematical Olympiad /37 of 47

Turkish Mathematical Olympiad

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 t≤2006/14t \le 2006/14. Now we will show that t≥2006/14t \ge 2006/14.
For 1≤i≤141 \le i \le 14, let aia_i denote the number of students who are acquainted with the iith\text{th} teacher, and for 1≤j≤20061 \le j \le 2006, let bjb_j denote the number of teachers who are acquainted with the jjth\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}∣=ai≥0|\{j : (i, j) \in T\}| = a_i \ge 0 and ∣{i:(i,j)∈T}∣=bj≥1|\{i : (i, j) \in T\}| = b_j \ge 1.
Assume that (io,jo)∈T(i_o, j_o) \in T satisfies the condition aio/bjo≥ai/bja_{i_o}/b_{j_o} \ge a_i/b_j for all (i,j)∈T(i, j) \in T. Adding the inequalities aio/bjo⋅1/ai≥1/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:ai≠0}aiai=∑{i:ai≠0}1≤14, \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/bjo≥2006/14a_{i_o}/b_{j_o} \ge 2006/14, and hence t≥2006/14t \ge 2006/14.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.