Maths Olympiad Prep

Library / AMC 10 B /9 of 14

AMC 10 B

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 1≤r<n1 \le r < n. For a given nn, there are (nr)\binom{n}{r} subsets, and (nr)\binom{n}{r} is maximized when r=⌊n2⌋r = \lfloor \frac{n}{2} \rfloor or r=⌈n2⌉r = \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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