0
$\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.

I guess pigeonhole principle must be applied but I cannot see how to move forward with it. So, let us consider the three languages (say, A, B and C) as pigeonholes. By pigeonhole principle, at least one of A, B and C must contain at least ceil(17/3) = 6 pigeons. So, 6 mathematicians must be there and all of them know the same language. I can only see this.

$\endgroup$
2
  • $\begingroup$ Can’t figure out the pair wise thing. It seems to me that if 6 people all know the same language, they can obviously communicate pairwise. But that can’t be it? $\endgroup$
    – user733666
    Jan 4, 2021 at 14:11
  • $\begingroup$ @DavidMitra This is Ramsey theory. Each language is a different coloured edge. See duplicate. $\endgroup$
    – Parcly Taxel
    Jan 4, 2021 at 14:30

1 Answer 1

Reset to default
0
$\begingroup$

Let's look at it from the perspective of Mathematician A.

By PHP, there will be at least $6$ mathematicians such that 'A' talks with all the mathematicians in the same language(Language L).

If you find any 2 mathematicians among those 6 mathematicians talking in language L we are done because then we found 3 people(A and the other 2 mathematicians) who speak in the same language pairwise

So basically 6 people have to talk in the other two languages

Hence the question simplifies to proving that 3 people talk in the same language pairwise with 6 mathematicians and 2 languages. Using the same argument as above, you can prove that.

$\endgroup$

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