2024 AMC 10B Problem 12

Suppose $n$ languages are spoken in total and every student speaks exactly $k$ of them. Each student corresponds to a $k$-element subset of the $n$ languages.

The condition says that for any two students, neither language set contains the other. Because all the sets have the same size $k$, one set contains another only when they are identical. So the condition is simply: all $100$ subsets are different.

Conversely, any $100$ distinct $k$-subsets work. So we need $\binom{n}{k} \ge 100$ for some $k$, and we want the smallest $n$. For fixed $n$ the largest binomial coefficient is the middle one:
$$\binom{8}{4} = 70 < 100, \qquad \binom{9}{4} = 126 \ge 100.$$
With $8$ languages no choice of $k$ gives $100$ different subsets, while with $9$ languages we can assign each student a different $4$-language subset.

The answer is $\boxed{\textbf{(A)}\ 9}$.

Translating "speaks a language the other does not" into set language turns a wordy condition into "no set contains another," and equal sizes collapse that to "all sets distinct." The problem is then just counting subsets, with the useful fact that $\binom{n}{k}$ peaks at $k = \lfloor n/2 \rfloor$. Look for hidden bijections between people and subsets whenever a problem describes who has what.

• Reading 'A speaks something B does not' as requiring disjoint sets, which leads to 100 languages; equal-size sets satisfy the condition as soon as they are different.
• Checking $\binom{8}{k}$ for only one value of $k$ (say $k = 2$) and not realizing that $k = 4$ is the best case for $n = 8$, so that $8$ really is impossible.