1
$\begingroup$

There are 17 mathematicians and 3 official languages. Every pair of mathematicians communicate in one of the official languages. Prove that there are 3 mathematicians communicating in the same language pairwise.

This is what I got: At least one language is spoken by 6 people.

However I'm not really sure about the term pairwise, do we need 3 or 6 people speaking the same language? Does it mean 3 people can communicate with each other by forming 3 pairs, but not all pairs have to be speaking the same language? If so then I have proven by saying 6 people can speak the same language.

$\endgroup$
6
  • 1
    $\begingroup$ I think you misunderstood the question. Since every pair communicate in one language, it may be possible for some mathematicians to speak more than one language. For example, if there are only 3 mathematicians $A,B,C$, perhaps $A$ and $B$ talk in English, $B$ and $C$ talk in French, $C$ and $A$ talk in Chinese. If so, you need to find, among the 17, $3$ mathematicians talking to each other in the same language. $\endgroup$
    – player3236
    Sep 27, 2020 at 18:46
  • 3
    $\begingroup$ What’s wanted is $3$ people who can all communicate with one another in the same language. See this section of the Wikipedia article on Ramsey’s theorem. $\endgroup$
    – Brian M. Scott
    Sep 27, 2020 at 18:47
  • $\begingroup$ I have proven that at least one language is spoken by 6 people, so have I solved it? $\endgroup$
    – MPP
    Sep 27, 2020 at 20:05
  • 1
    $\begingroup$ @MingPokNg No you have not solved it. You could have six people arranged in a hexagon, each speaking English to the people either side of them, and a mixture of Gobbledygook and Quenya to the three remaining people, without having three people, all communicating with each other in the same language. There are $136$ conversations - each of which will be in one of the three languages. The question is about assigning languages to conversations, not to people - I think that is why you are confused. $\endgroup$
    – tkf
    Sep 27, 2020 at 21:54
  • 3
    $\begingroup$ @BrianM.Scott's comment is on point here. This is a problem in Ramsey theory. You can think of it as a problem in graph theory. There are $17$ vertices in a complete undirected graph, so there are $\binom{17}{2} = 136$ edges. Each of the edges is colored either red, green, or blue (say), with each color representing one of the three languages. Then you must prove that there is a single-color triangle (i.e., a triangle where all three edges are the same color). If there were only two languages, just six people would suffice to guarantee a monochromatic triangle—but there are three languages. $\endgroup$
    – Brian Tung
    Jul 25, 2022 at 3:51

1 Answer 1

Reset to default
2
$\begingroup$

This is also an old IMO problem. Posting a CW solution to get this off the list of unanswered questions.

Pick a mathematician, call them $X_0$. There are $16$ other mathematicians, and $16/3>5$, so $X_0$ is discussing with at least six others in the same language. Without loss of generality we can assume that they discuss in language $A$ with $X_1,X_2,\ldots,X_5$ and $X_6$. If any pair $X_i,X_j, 1\le i<j\le6$, also uses language $A$ in their mutual communication, then we have found our triple, $X_1,X_i,X_j$. So we can assume that every pair $\{X_i,X_j\}, 1\le i<j\le6$, uses either language $B$ or language $C$ in their communication.

We have thus simplified the problem to a set of six mathematicians and two languages. Let's repeat the dose. Pick a mathematician, say $X_1$. With the five peers $X_2,\ldots,X_6$ they are using the same language (only two choices) with at least three others. Again without loss of generality we can assume that $X_1$ communicates in $B$ with all of $X_2,X_3,X_4$. If any two of $X_2,X_3,X_4$ use language $B$ in their mutual correspondence, then we have again found our triple.

The remaining possibility is that in their pairwise communication all three of $X_2,X_3,X_4$ use language $C$. But then they form the required triple.

$\endgroup$
4
  • $\begingroup$ How old is "old"? This seems like it must be quite old—but I'm interested in something a bit more precise than "quite" old. :-P $\endgroup$
    – Brian Tung
    Jul 26, 2022 at 20:34
  • $\begingroup$ @BrianTung I recall having seen in a book written by my former IMO coach. The book was printed in 1975 (?). The contents consisted of IMO problems up to that date (and their solutions). I'm afraid I cannot put a more precise date on it. I don't have a personal copy, but there may be one at the library. If I find it I will look it up. Anyway, the problem appeared before 1975. $\endgroup$
    – Jyrki Lahtonen
    Jul 27, 2022 at 5:18
  • $\begingroup$ This is obviously intended to be a problem in Ramsey theory., but the story makes little sense. If A & B can communicate in English, and if C & D can communicate in English, why wouldn't A & C be able to communicate in English? I suppose you could say they are speaking different dialects of English. But then what is so interesting about $3$ people communicating with one another in the same language, if they are speaking $3$ mutually incomprehensible dialects? If the organizers can't come up with a better story than that, maybe they should skip the stories and just set straight math problems. $\endgroup$
    – bof
    Aug 10, 2022 at 6:16
  • 1
    $\begingroup$ A fair question @bof. In the original IMO form the question had the mathematicians corresponding. Each pair restricting their correspondence to one of three topics. The same remark applies. The question designers would be better off simply using a collection of 17 points, each pair connected with one of blue, red or green edge etc. $\endgroup$
    – Jyrki Lahtonen
    Aug 10, 2022 at 8:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .