Question

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?

$9$

$10$

$12$

$51$

$100$

Solution:

Give each student the set of languages they speak. The condition says no one's set sits inside another's. Everyone speaks the same number $k$ of languages, and two distinct $k$ -element sets can never contain each other, so all we need is $100$ different $k$ -subsets of the $n$ languages, i.e. $\binom{n}{k} \ge 100.$ With $n = 8$ the best we can manage is $\binom{8}{4} = 70,$ short of $100.$ But $\binom{9}{4} = 126 \ge 100.$ So $9$ languages are both enough and necessary. Therefore, the answer is A.

2024 AMC 10B Problem 12

Solution:

Problem 12 in Other Years