Problem:
A group of 100 students from different countries meet at a mathematics competition. Each student speaks the same number of languages, and, for every pair of students A and B, student A speaks some language that student B does not speak, and student B speaks some language that student A does not speak. What is the least possible total number of languages spoken by all the students?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Suppose the languages spoken are labeled . Note that the collection of all subsets of of size will satisfy the conditions in the problem for any in the range . For a given , there are subsets, and is maximized when or .
If and , the number of distinct subsets is , so . But , so is the least possible total number of languages spoken by all the students.
Note: The restriction on having the students speak the same number of languages is not needed. A collection of subsets of a given set with elements satisfying the condition that no member of the collection is a subset of another is called an antichain. Sperner's Theorem asserts that the largest antichain occurs when the subsets are all of size , where or .
The problems on this page are the property of the MAA's American Mathematics Competitions