In a conference, mathematicians from $11$ different countries participate and they have integer-valued ages between $27$ and $33$ years (including $27$ and $33$). There is at least one mathematician from each country, and there is at least one mathematician of each possible age between $27$ and $33$. Show that we can find at least five mathematicians $m_1, \ldots, m_5$ such that for any $i \in \{1, \ldots, 5 \}$ there are more mathematicians in the conference having the same age as $m_i$ than those having the same nationality as $m_i$. Proposed by S. Muralidharan
Problem
Source: India IMOTC Practice Test 1 Problem 3
Tags: combinatorics
31.05.2024 12:05
Let $A$ be the set of possible ages and $B$ the set of countries. Then $|A|=7, |B|=11$. We represent a mathematician as an edge between $A$ and $B$. We prove that there exist $5$ edges such that for each of them $e=ab$ it holds $d(a)>d(b)$. It's possible that two vertices are connected with more than one edge, but we'll prove this even if it's a simple graph. The proof is based on the following claim. Lemma. A bipartite graph $G(A,B)$ with $|B|>|A|$ is given. To each edge is assigned a positive number. Prove that there exists an edge $a\,b, a\in A, b\in B$ such that the sum of numbers on the edges incident with $a$ is greater than the sum of numbers on the edges incident with $b$. One can see a proof here in my blog. Let's apply the lemma consecutively 5 times. We take an edge $e=ab, d(a)>d(b)$ and delete the vertex $b$. It's possible that after deleting $b$ some vertex in $A$ becomes isolated in which case we delete it. Thus, We obtain a graph with $|B|=10$ and $|A|\le 7$. After this operation is done $4$ times and four vertices $b_1,b_2,b_3,b_4$ are removed, there remains a graph $G'(A',B')$ with $|B'|=7, |A'|\le 7$. If $|A'|<7$, we can do the operation again, so suppose $A=A'$. Assume $b_1$ was connected with $a'\in A'=A$. Since $a'$ is not isolated in $G'$, there is an edge $e'=a'b'\in E(G')$. Now, we cannot apply the lemma directly, but we can proceed in the same way as in its proof. Assume on the contrary $d_{G'}(a)\le d_{G'}(b), \forall a\in A', b\in B'$. But for $e=a'b'$ we must have $d_{G'}(a')< d_{G'}(b')$ because if $d_{G'}(a')= d_{G'}(b')$ then adding the edge $a'b_1$ we get $d_{G}(a')> d_{G}(b')$. So, doing exactly the same trick as in the proof of the lemma we, arrive at a contradiction.
31.05.2024 12:38
@ above, Does this has to do something with alg graph theory?
28.09.2024 15:30
In the following table the cell at the intersection of $i$th row and $j$th column is the number of mathematicians with age $i$ and from country $C_j$. \begin{tabular}{|c|c|c|c|c|c|} \hline &$C_1$ & $C_2$ &$\cdots$ & $C_{11}$& \\ \hline 27 & $a_{1,1}$ & $a_{1,2}$ & $\cdots$ & $a_{1,11}$ & $r_1$\\ \hline 28 & $a_{2,1}$ & $a_{2,2}$ & $\cdots$ & $a_{2,11}$& $r_2$\\ \hline $\cdots$ &$\cdots$ & $\cdots$ & $\cdots$ & $\cdots$& $r_i$\\ \hline 33 & $a_{7,1}$ & $a_{7,2}$ & $\cdots$ & $a_{7,11}$ &$r_7$\\ \hline & $c_1$ & $c_2$ & $\cdots$ & $c_{11}$ & \\ \hline \end{tabular} Consider \begin{align*} \sum_{i=27}^{33} \sum_{j=1}^{11} a_{i,j} \left(\dfrac{1}{c_j} - \dfrac{1}{r_i}\right) &= \sum_{i=27}^{33} \sum_{j=1}^{11} \dfrac{a_{i,j}}{c_j} - \sum_{i=27}^{33} \sum_{j=1}^{11}\dfrac{a_{i,j}}{r_i}\\ &= \sum_{j=1}^{11} \dfrac{1}{c_j} \sum_{i=27}^{33} a_{i,j} - \sum_{i=27}^{33} \dfrac{1}{r_i} \sum_{j=1}^{11} a_{i,j}\\ &= \sum_{j=1}^{11} \left(\dfrac{1}{c_j} \cdot c_j \right)- \sum_{i=27}^{33} \left(\dfrac{1}{r_i} \cdot r_i\right) \\ &= \sum_{j=1}^{11} 1 - \sum_{i=27}^{33} 1 \\ &= 4 \end{align*}Since $\frac{1}{c_j} - \frac{1}{r_i} < 1$, considering the term $a_{i,j} \left(\frac{1}{c_j} - \frac{1}{r_i}\right)$ as sum of $a_{i,j}$ terms $\frac{1}{c_j} - \frac{1}{r_i}$, it follows that there are at least five such terms that are positive. Thus there are at least five mathematicians satisfying the requirement.\qed Remark. In general, if there were $m$ countries and $n$ different possible ages, there would be at least $m-n+1$ mathematicians satisfying the requirement.