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 and , student speaks some language that student does not speak, and student speaks some language that student does not speak. What is the least possible total number of languages spoken by all the students?
Pick one
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.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.