Maths Olympiad Prep

Library / /11 of 18

Combinatorics Difficulty 4.5 AIME Find the answer United States

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 AA and BB, student AA speaks some language that student BB does not speak, and student BB speaks some language that student AA 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 L1,L2,L3,,LnL_1, L_2, L_3, \dots, L_n. Note that the collection of all subsets of {L1,L2,L3,,Ln}\{L_1, L_2, L_3, \dots, L_n\} of size rr will satisfy the conditions in the problem for any rr in the range 1r<n1 \le r < n. For a given nn, there are (nr)\binom{n}{r} subsets, and (nr)\binom{n}{r} is maximized when r=n2r = \lfloor \frac{n}{2} \rfloor or r=n2r = \lceil \frac{n}{2} \rceil.

If n=8n = 8 and r=4r = 4, the number of distinct subsets is (84)=70<100\binom{8}{4} = 70 < 100, so n>8n > 8. But (94)=(95)=126>100\binom{9}{4} = \binom{9}{5} = 126 > 100, so n=9n = 9 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.