On an international conference there are 4 official languages. Each two of the attendees can have a conversation on one of the languages. Prove that at least 60% of the attendees can speak the same language.
Problem
Source: V International Festival of Young Mathematicians Sozopol 2014, Theme for 10-12 grade
Tags: combinatorics
23.10.2019 15:37
As usual, let $G=(A,L)$ be the corresponding bipartite graph for the set $A$ of $n$ attendees and the set $L$ of four languages $\{\ell_1,\ell_2,\ell_3,\ell_4\}$. If there is an attendee who knows only one language, we are done since all the others also know that language. So, suppose any person knows at least two languages. Let $A_2\subset A$ be the subset of attendees that know exactly $2$ languages, and $A_3\subset A$ - those of them knowing at least $3$ languages. Let $|A_2|=k$. We consider the following two cases. a) Suppose $k\leq \frac{3}{5}n$. We estimate the number of edges $|E|$ of $G$ as follows: $$|E|\geq 2k+3(n-k)=3n-k\geq \frac{12}{5}n$$It means there is a vertex in $L$ with degree at least $\frac{12}{5\cdot 4}n=\frac{3}{5}n$, hence at least $60$% of attendees know that language. b) $k>\frac{3}{5}n$. Consider the pairs of languages known by the persons in $A_2$. There are $6$ possible $2$ element subsets of $L$. If an attendee in $A$ knows, say, $\ell_1$ and $\ell_2$, then no other in $A_2$ knows both $\ell_3,\ell_4$. Having this in mind, it follows the number of all pairs of languages known by persons in $A_2$ are at most $3$. If these $3$ pairs (at most) have an non-empty intersection, we are done, since $k>\frac{3}{5}n$. Otherwise the only possibility, up to rearrangement of the languages, is $\{\ell_1,\ell_2\}, \{\ell_2,\ell_3\},\{\ell_1,\ell_3\}$. Denote the set of those three pairs as $P$. So any person in $A_2$ knows one pair of languages in $P$ . Any attendee in $A_3$ knows at least three languages, hence he/she also knows at least one pair in $P$. Thus, we map each attendee to one of the pairs in $P$. It follows, there are two pairs in $P$ mapped to at least $2/3$ of attendees. The result follows for the language that meet the two pairs.