Nine mathematicians meet at an international conference and discover that among any three of them, at least two speak a common language. If each of the mathematicians speak at most three languages, prove that there are at least three of the mathematicians who can speak the same language.
Problem
Source:
Tags: AMC, USA(J)MO, USAMO, pigeonhole principle, floor function, Ramsey Theory
16.08.2011 22:49
Let the delegates be represented as the vertices $d_1,d_2,\ldots ,d_9$ with an edge between $d_i$ and $d_j$ in the $i$-th colour iff $d_i$ and $d_j$ both can speak the $i$-th language. If $d_1$ is adjacent to all other $d_i$, then we are done - all the edges incident to $d_1$ (of which there are 8) are one of at most three colours, so pigeonhole assures that one colour is repeated. So assume $\{d_1,d_2\}$, $\{d_1,d_3\}$ have the same colour. Then $d_1,d_2,d_3$ all speak said language. Otherwise assume there is no edge between $d_1$ and $d_9$ (WLOG). From the condition that for any three delegates, two speak a common language, considering the three vertices $d_1,d_9,d_i$ for $2\le i \le 9$ implies that if $x_1,x_9$ are the number of edges from $d_2,d_3,\ldots ,d_8$ to $d_1,d_9$ respectively then $x_1+x_9\ge 7$ so WLOG $x_1\ge 4$. So there are 4 edges connecting $d_1$ to 4 of $d_2,d_3,\ldots ,d_8$, by the pigeonhole principle, two of these edges have the same colour. Then we have our desired monochromatic triangle.
30.01.2012 05:07
added 5/4: Possibly with help from or using http://mks.mff.cuni.cz/kalva/usa/usoln/usol785.html
23.10.2014 05:52
23.10.2014 09:20
There are some strange things about your "proof", for example when passing from an upper bound for the degree of one vertex to some statement about the degrees of all the vertices. The main flaw however is that the presence of a triangle is not equivalent to three people speaking the same language; for triangle $ABC$ maybe $A,B$ speak language $1$, $B,C$ speak language $2$, and $C,A$ speak language $3$.
11.01.2015 02:28
We may however apply some famous theorem. Say there is a blue edge between two delegates if they share a common language, and a red edge otherwise. The graph contains no red triangle, so by TurĂ¡n's theorem there are at most $4\cdot 5 = 20$ red edges (when the graph is bipartite, with two shores of $4$, respectively $5$ vertices, and with all red edges between different shores). Then there are at least $\binom {9} {2} - 20 = 16$ blue edges. By an averaging argument, that means that at least at one vertex $x$ meet four blue edges. But then $x$ shares a language with two of his neighbours. With only $8$ delegates the result stands no more. Say $4$ delegates speak respectively languages $abc, adf, bef, cde$, and the other $4$ delegates speak respectively languages $a'b'c', a'd'f', b'e'f', c'd'e'$. In this model every condition is respected, but each language is spoken by exactly two delegates. As a final remark, the fact that the Ramsey number coincidentally is $R(3,4) = 9$ does not help. Having no red triangle means there is a blue $K_4$, but that creates no contradiction (as the model above shows).
23.12.2015 22:12
Define graph on mathematicians, two people connected if both cannot speak same language Then condition is there is no triangle If $A$, $B$ be two mathematicians, then they may be connected each other, and for each $7$ people, connected to at most one $A$, $B$ Thus $deg(A) + deg(B) \le 7 + 2 = 9$ By friend Pigeonhole Principle we assume WLOG $deg(A) \le 4$ Then $A$ speak common language with at least $4$ other mathematicians But he speak at most $3$ language! By friend Pigeonhole Principle he speak same language with $2$ people Then these $3$ people speak same language Q.E.D
11.04.2018 01:46
why did this take me over an hour and why is my solution less efficient than everyone else's in this thread Suppose for the sake of contradiction that there do not exist three mathematicians who speak the same language. Consider the graph on the mathematicians defined such that there is an edge between two mathematicians iff they speak the same language. Since $R(3,4) = 9$, and we know there does not exist an independent set of size $3$, there must exist a $4$-clique. Note that by our assumption no two edges can be connected via the same language (else by transitivity we obtain a "monochromatic" triangle!). This means there are six distinct languages represented by this group. It is also clear that each person must speak three languages in this group. Now we claim that the remaining five people must form a 5-clique. To prove this, take any two people $P_1$ and $P_2$ not in this clique and consider the triangle formed by these two people and one of the people $P$ in the clique. We know by the assumption that two of these people must speak a common language. But if it is the case that $P_1$ and $P$ have a common language, say $k$, then $P_1$, $P$, and the person in the 4-clique having a common language $k$ with $P$ yield a contradiction. Thus $P_1$ and $P_2$ must be connected with each other. Repeating this for all ten pairs gives the desired five-clique $\{Q_1,Q_2,Q_3,Q_4,Q_5\}$. This gives trouble, since per our assumption each of the links between $Q_1$ and $Q_j$ for $2\leq j\leq 5$ must be from a different language, implying $Q_1$ speaks at least four languages. EDIT: ... annndddd immediately after posting this and looking through the other solutions I realize that one of my ideas from thinking about this problem finishes really easily. -.- Looks like it's the same as mavropnevma's though.
11.04.2018 05:49
Number the people. If any two people speak a common language, the result is obvious, so suppose WLOG that person 1 and 2 do not speak a common language. Then people 3 through 9 each speak a common language with at least one of these people, so at least four people speak a common language with say person 1 (by Pigeonhole). However, again by Pigeonhole, two of these people speak the same common language, so these three people all speak a common language.
13.05.2020 10:50
Great Solution Phie11!
23.10.2020 08:02
15.04.2023 07:32
suli wrote: Define graph on mathematicians, two people connected if both cannot speak same language Then condition is there is no triangle If $A$, $B$ be two mathematicians, then they may be connected each other, and for each $7$ people, connected to at most one $A$, $B$ Thus $deg(A) + deg(B) \le 7 + 2 = 9$ By friend Pigeonhole Principle we assume WLOG $deg(A) \le 4$ Then $A$ speak common language with at least $4$ other mathematicians But he speak at most $3$ language! By friend Pigeonhole Principle he speak same language with $2$ people Then these $3$ people speak same language Q.E.D Very nice solution! Yeah, I did the same thing, my key idea was just to use Pigeonhole, since the problem conditions with graph theory suggest that.
07.01.2024 07:35
Let the mathematicians be called $x_1,x_2,\cdots,x_9$. If a mathematician shares a language with $\geq4$others, $\exists$ $ 3$ mathematicians who speak a common language. Assuming, for the sake of contradiction, that no $3$ mathematicians speak the same language. $\therefore$ Every mathematician shares a language with $\leq 3$ others $\Rightarrow$ He does not share any language with $\geq5$ others. Let us consider $x_1$. He shares with $x_2,x_3,x_4$. Thus he does not share with $x_5,x_6,x_7,x_8,x_9$ (worst case scenario). Also if $x_5$ does not share a language with $\geq5$ others he can share a language with at most $3$ out of the set ${x_6,x_7,x_8,x_9}$. Let they be $x_6,x_7,x_8$. $\therefore$ $x_5$ does not share a language with $x_9$. Also, $x_1$ does not share a language with $x_9$. $x_5$ does not share a language with $x_1$. But then in $(x_1,x_5,x_9)$, no two of them speak a common language, which contradicts the problem. $(\Rightarrow\Leftarrow)$. Thus our assumption was wrong, and $\exists$ at least $3$ mathematicians speaking a common language.