2024 AMC 10B Problem 12

P11-15~4 minPrint

Basic Counting Sets, Estimation & Miscellaneous Map the objects to something easier to count Bound the quantity above/below or estimate to pin it down

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?

Show solution without answering

Key insight

All students speak the same number of languages, so the rule just says no two students speak exactly the same group. Choosing 4 of 9 languages gives 126 groups.

Solution

1. Understand the rule. Say every student speaks $3$ languages. If student $A$ speaks French, German, Hindi and student $B$ speaks French, German, Korean, then $A$ has Hindi (which $B$ lacks) and $B$ has Korean (which $A$ lacks). The rule holds.
2. When would the rule fail? Only if one student's languages were all included in the other's. Since both students speak the same number of languages, that can only happen when they speak exactly the same languages.
3. So the rule simply says: no two students speak exactly the same group of languages.
4. Count the groups. Suppose there are $n$ languages and each student speaks $k$ of them. The number of different groups is " $n$ choose $k$ ", written $\binom{n}{k}$ . We need at least $100$ different groups, one per student.
5. Try $9$ languages. Choosing $4$ of $9$ :
$\binom{9}{4} = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} = 126.$
That is at least $100$ , so give each student a different group of $4$ languages. This works.
6. Show $8$ languages is not enough. With $8$ languages, the number of groups for each choice of $k$ is:

$k$	1	2	3	4	5	6	7	8
$\binom{8}{k}$	8	28	56	70	56	28	8	1

The largest is $70$ , less than $100$ . With fewer than $8$ languages there are even fewer groups. So $8$ or fewer languages cannot work.

Nine languages work and eight do not, so the least total is $9$ .

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

Why this works

The wordy condition "each speaks something the other does not" becomes simple once you notice everyone speaks the same number of languages: it just means all the groups are different. Then the problem is only about counting groups. For a fixed number of languages, the most groups come from choosing about half of them, which is why $k = 4$ is the right choice.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Intermediate Counting & Probability, Chapter 2: Sets and Logic (§2.2, §2.3)
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques