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?
AMC 10 B
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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.