There are n boys and m girls at Daehan Mathematical High School. Let $d(B)$ a number of girls who know Boy $B$ each other, and let $d(G)$ a number of boys who know Girl $G$ each other. Each girl knows at least one boy each other. Prove that there exist Boy $B$ and Girl $G$ who knows each other in condition that $\frac{d(B)}{d(G)}\ge\frac{m}{n}$.
Problem
Source: Korea National Olympiad P3
Tags: combinatorics, graph
24.11.2020 07:55
We use the usual graph notations. ($H(B,G)$ is a bipartite graph.) Write $\frac{1}{d(g)}$ on each edge $\{b,g\} \in E(H)$. The sum of the numbers is $|G|$, so there exists some $b\in B$ such that $\sum_{\{b,g\}\in E(H)} \frac{1}{d(g)} \ge \frac{|G|}{|B|}$. Again by PHP there exists some $g$ adjacent to $b$ satisfying $\frac{1}{d(g)}\ge \frac{|G|}{|B|} \times \frac{1}{d(b)}$, so we're done.
24.11.2020 08:23
Does this work? Assume FTSOC that there exist no $B,G$ so that $d(B)/d(G)\ge m/n$. This means that $d(B)/d(G)<m/n \forall B,G \in S$, where $S$ is the set of people at the school. Next, note that $d(B_1)+d(B_2)+\dots+d(B_n)=d(G_1)+d(G_2)+\dots+d(G_m)$, because if a girl knows a boy, then that boy knows that girl. Summing over all pairs $B,G\in S$, $(d(B_1)+d(B_2)+d(B_3)+\dots+d(B_n))(\frac{1}{d(G_1)}+\frac{1}{d(G_2)}+\dots+\frac{1}{d(G_m)})<m^2$. However, \begin{align*} (d(B_1)+d(B_2)+d(B_3)+\dots+d(B_n))(\frac{1}{d(G_1)}+\frac{1}{d(G_2)}+\dots+\frac{1}{d(G_m)}) &= (d(G_1)+d(G_2)+\dots+d(G_m))(\frac{1}{d(G_1)}+\frac{1}{d(G_2)}+\dots+\frac{1}{d(G_m)}) \\ &\ge (\underbrace{1+1+1+\dots+1}_{m \phantom{j} 1's})^2 \\ &= m^2. \end{align*}This is obviously a contradiction, so we have shown that $d(B)/d(G)\ge m/n$ for at least $1$ pair $B,G$.
24.11.2020 21:16
@above I think it's flawed. The problem requires $B$ and $G$ to know each other.
25.11.2020 12:29
Note that this can be generalized in the following way. In each cell of a table with $m$ rows and $n$ columns, where $m<n$, we put a non-negative real number such that each column contains at least one positive number. Show that there is a cell with a positive number, such that the sum of the numbers in its row is larger or equal than the sum of the numbers in its column multiplied by $\frac{n}{m}$. The OP is just the case when all the numbers are $1$'s and we can interpret the table as the adjacency matrix of a graph. Something slightly weaker was given at Bundeswettbewerb Mathematik 2020, Round 2 - Problem 4.
25.11.2020 14:47
I think we can employ incidence matrices
14.02.2021 00:02
We randomly pick some boy $B$ and some girl $G$ Note that: $$\mathbb{E}(d(B)) n = \text {(total number of boy-girl friendships)} = \mathbb{E}(d(G)) m$$So, $$ \frac{\mathbb{E}(d(B))}{ \mathbb{E}(d(G))} = \frac{m}{n}$$ There is always some boy $B^*$ and girl $G^*$ such that $$d(B^*) \ge \mathbb{E}(d(B)), d(G^*) \le \mathbb{E}(d(G))$$ Hence, $$\frac{d(B^*)}{d(G^*)}\ge\frac{m}{n}$$for some $B^*, G^*$ Note: Please tell me if I made a mistake.
14.02.2021 15:45
I think, the probability approach is unnecessary. You just take the corresponding average degrees. But this is not an issue. The issue is that you cannot guarantee $B^*$ and $G^*$ know each other. This is the main point, without it the problem is trivial.
30.01.2022 21:24
kred9 wrote: Does this work? Assume "FTSOC"that there exist no $B,G$ so that $d(B)/d(G)\ge m/n$. This means that $d(B)/d(G)<m/n \forall B,G \in S$, where $S$ is the set of people at the school. Next, note that $d(B_1)+d(B_2)+\dots+d(B_n)=d(G_1)+d(G_2)+\dots+d(G_m)$, because if a girl knows a boy, then that boy knows that girl. Summing over all pairs $B,G\in S$, $(d(B_1)+d(B_2)+d(B_3)+\dots+d(B_n))(\frac{1}{d(G_1)}+\frac{1}{d(G_2)}+\dots+\frac{1}{d(G_m)})<m^2$. However, \begin{align*} (d(B_1)+d(B_2)+d(B_3)+\dots+d(B_n))(\frac{1}{d(G_1)}+\frac{1}{d(G_2)}+\dots+\frac{1}{d(G_m)}) &= (d(G_1)+d(G_2)+\dots+d(G_m))(\frac{1}{d(G_1)}+\frac{1}{d(G_2)}+\dots+\frac{1}{d(G_m)}) \\ &\ge (\underbrace{1+1+1+\dots+1}_{m \phantom{j} 1's})^2 \\ &= m^2. \end{align*}This is obviously a contradiction, so we have shown that $d(B)/d(G)\ge m/n$ for at least $1$ pair $B,G$. What isFTSOC?
15.02.2022 19:45
For the sake of contradiction
15.02.2022 21:40
This was also Turkey MO 2006.