There are $2006$ students and $14$ teachers in a school. Each student knows at least one teacher (knowing is a symmetric relation). Suppose that, for each pair of a student and a teacher who know each other, the ratio of the number of the students whom the teacher knows to that of the teachers whom the student knows is at least $t.$ Find the maximum possible value of $t.$
Problem
Source: Turkey National Olympiad 2006 - D1 - P2
Tags: ratio, graph theory, combinatorics unsolved, combinatorics
07.01.2007 15:56
Can you explain more clearly about the question ? Thx..
08.01.2007 18:48
it is a question that hard to understand and i have got no time to explain but i will do it in a few days thx for your attention you are the one that pay attention to question
14.01.2007 09:00
i can give an example think about that max of t is 144 and also think that every children knows every teacher so the ratio will be 2006/14 for every pair so there arent any pair s.t. the ratio is at least 144.
15.01.2007 01:01
The wording of the question is unclear -- do you think you could try to re-explain the setup? Thanks.
11.03.2007 00:00
Think about a set $S$, consisting ordered pairs. $A=({{{a_{1},\ldots,a_{14}}})}$ and $B=({{{b_{1},\ldots,b_{2006}}})}$ are given sets such that if $(a,b)\in{S}$ then $a\in{A}$ and $b\in{B}$. Also for every $b\in{B}$, there is an $a\in{A}$ such that $(a,b)\in{S}$.For every $b\in{B}$, $s_{b}$ is the number of the $(a_{i},b)$ pairs such that $(a_{i},b)\in{S}$ and for every $a\in{A}$, $t_{a}$ is the number of the $(a,b_{i})$ pairs such that $(a,b_{i})\in{S}$. $t$ is a real number such that (whatever $S$ is) for every $(a,b)\in S$, $\frac{t_{a}}{s_{b}}\le{t}$. Find the minimum value of $t$.
22.11.2012 18:10
Define teachers and students as graph vertices and knowing relations as edges. Let $t_i, s_i$ represent the degree of teachers and students, respectively. If we construct a complete bipartite graph, we obviously observe that $t\le \frac{2006}{14}$. We'll prove that the given bound is reachable. Suppose not, let $G$ doesn't satisfy the condition. Then for all $t_i$ and $s_j $, $\frac{t_i}{s_j}< \frac{2006}{14}$. Summing up gives \[\sum t_i \sum \frac{1}{s_i}<\frac{2006}{14}.2006.14=2006^2\] also note that $\sum t_i=\sum s_i$ therefore, \[2006^2\le \sum s_i \sum \frac{1}{s_i}< 2006^2\] which is a contradiction so the desired constant is $\frac{2006}{14}$.
11.03.2018 23:49
Let $a_i:i=1,2,\dots,14$; and, $b_j:j=1,2,\dots,2006$ respectively denote the number of students, known to teacher $i$, and, the number of teachers, known by student $j$. Let, $(i,j)\in E$ iff $i$ and $j$ know each other (think of this as a bipartite graph, with one independent set teachers; and one students). First observation, $$ a_i = |\{j:(i,j)\in E\}| \quad \text{and}\quad b_j = |\{i:(i,j)\in E\}|. $$With this logic, notice that in the case where $a_i=2006,\forall i$, and, $b_j = 14,\forall j$, the ratio $t$ is $2006/14$. Hence, the best $t \leq \frac{2006}{14}$. Now, we claim that, in any such bipartite graph, there is an edge $(i,j)$, such that, $\frac{a_i}{b_j}\geq \frac{2006}{14}$. Suppose that, this is false. Observe, $$ \frac{1}{b_j}<\frac{2006}{14}\frac{1}{a_i} \implies \sum_{j:(i,j)\in E}\frac{1}{b_j} < \frac{2006}{14}\underbrace{\sum_{j:(i,j)\in E} \frac{1}{a_i}}_{=1} = \frac{2006}{14}. $$Now, let's carry out another summation, over all $i$'s: $$ \sum_{i=1}^{14}\sum_{j:(i,j)\in E}\frac{1}{b_j}<2006. $$Now, swap the order of the summation above (with redefined indices, the outer sum running over $j=1:2006$, and the inner sum over $i:(i,j)\in E$), and get, $$ \sum_{j=1}^{2006}\frac{1}{b_j}\underbrace{\sum_{i:(i,j)\in E} 1}_{=b_j} <2006, $$giving us a desired contradiction.