4
$\begingroup$

At a party of $250$ mathematician , each mathematician speaks one or more languages. It is found that for any two mathematicians, each speaks at least one language not spoken by other. Show that there are at least $10$ different languages spoken in the party.

I have a feeling that Pigeon Hole Principle to be used, but I am clueless how to use it. Please help.

$\endgroup$
  • $\begingroup$ Do you know Sperner's theorem? $\endgroup$ – Mirko Jan 31 '17 at 10:11
2
$\begingroup$

It's more complicated than that, and you need to use Sperner's Theorem.

If you consider the set of languages spoken by each mathematician, you know that

  1. all these sets are different, and
  2. none of the sets is a subset of another.

This makes it a Sperner family (antichain), and the theorem gives the maximum size of such a family.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.