AMC 10 · 2024 · #12

Grade 8 arithmetic

Archetype Small-Domain Constrained Search

combinations-basicset-partitionlogical-deduction easier-related-problembound-inequality-then-enumeratecomplementary-counting ↑ Prerequisites: combinations-basicset-partition

📏 Medium solution 💡 3 insights

Problem

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?

$\textbf{(A) } 9 \qquad\textbf{(B) } 10 \qquad\textbf{(C) } 12 \qquad\textbf{(D) } 51 \qquad\textbf{(E) } 100$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

100

View mode:

Toolkit + CCSS Solution

Understand

Restated: There are $100$ students. Every student speaks the same number of languages, say $k$. For any two students, each one knows a language the other does not. Find the smallest total number of distinct languages $n$ that the group could collectively speak.

Givens: $100$ students total; Every student speaks the same number $k$ of languages; For any pair $(A, B)$, $A$ speaks something $B$ doesn't AND $B$ speaks something $A$ doesn't; Answer choices: (A) $9$, (B) $10$, (C) $12$, (D) $51$, (E) $100$

Unknowns: The minimum total number $n$ of distinct languages

Understand

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #6 Guess and Check, #16 Change Focus / Complement

The condition "each speaks something the other does not" sounds verbal, but it has a clean set-theoretic meaning: if both students speak exactly $k$ languages and neither set is a subset of the other, then the two sets must be different. Tool #9 (Easier Related Problem) handles the abstraction — drop the problem to small cases: with $n=2$ languages and $k=1$ per student, you can have at most $\binom{2}{1} = 2$ distinct students; with $n=3$, at most $\binom{3}{1} = 3$ or $\binom{3}{2} = 3$. The pattern is "max students $= \binom{n}{k}$". Tool #6 (Guess and Check) then walks $n = 7, 8, 9$ to find where $\binom{n}{k}$ first reaches $100$ — pick $k$ near $n/2$ to maximize. Tool #16 (Complement) reframes the awkward "each speaks something the other doesn't" as the simpler "the two sets are not nested," which is automatic once the sets are equal-sized and distinct.

Execute — Answer: A

#16 Change Focus / Complement 7.SP.C.8 Step 1

Translate the language condition into set language.
Let $L_A$ be the set of languages student $A$ speaks.
"$A$ speaks something $B$ doesn't" means $L_A \not\subseteq L_B$, and "$B$ speaks something $A$ doesn't" means $L_B \not\subseteq L_A$.
Combined with $|L_A| = |L_B| = k$, this is equivalent to saying $L_A \neq L_B$: two same-size sets are nested only if they are equal, so "not nested" $=$ "not equal".

$$|L_A| = |L_B| = k \;\text{ and }\; L_A \neq L_B \;\Longleftrightarrow\; \text{condition holds}$$

💡 If two equal-sized sets are nested, they are equal. So "not nested" simplifies to "not equal" — a single check, not two.

#9 Solve an Easier Related Problem 7.SP.C.8 Step 2

Smaller case to see the structure.
With $n$ languages available, the number of distinct $k$-element subsets is $\binom{n}{k}$.
So the number of students supported by $(n,k)$ is at most $\binom{n}{k}$.
For $n=3$: $\binom{3}{1}=3$, $\binom{3}{2}=3$, max $3$ students.
For $n=4$: $\binom{4}{2}=6$, max $6$ students.
The bound $\binom{n}{k}$ is the entire story.

$$\#\text{students} \leq \binom{n}{k}$$

💡 Reduce $100$ students to $3$ or $4$, watch how the counts work, and the general bound $\binom{n}{k}$ jumps out — Polya's principle of analogy.

#9 Solve an Easier Related Problem 8.EE.A.1 Step 3

Set up the search.
We need the smallest $n$ such that $\binom{n}{k} \geq 100$ for some $k$.
For each $n$, $\binom{n}{k}$ is biggest when $k$ is closest to $n/2$, so it's enough to maximize over $k$ near $n/2$.

$$\min \{ n : \max_{k} \binom{n}{k} \geq 100 \}$$

💡 The central binomial coefficient $\binom{n}{\lfloor n/2\rfloor}$ is the largest entry in row $n$ of Pascal's triangle, so checking only that one decides the row.

#6 Guess and Check 7.SP.C.8 Step 4

Guess and check $n = 7, 8, 9$.
$\binom{7}{3} = 35 < 100$.
$\binom{8}{4} = 70 < 100$.
$\binom{9}{4} = 126 \geq 100$.
So $n = 9$ is the first row of Pascal's triangle whose middle entry reaches $100$, and $k = 4$ works.

$$\binom{7}{3}=35,\; \binom{8}{4}=70,\; \binom{9}{4}=126$$

💡 Try the next $n$ each time — Pascal's triangle roughly doubles per row, so we cross $100$ fast and predictably.

#9 Solve an Easier Related Problem 7.SP.C.8 Step 5

Verify the construction.
With $n = 9$ languages and $k = 4$, pick any $100$ distinct $4$-element subsets out of the $126$ available, and assign one to each student.
All sets have the same size $4$ and are pairwise distinct, hence not nested, hence the condition holds.

$$n = 9, \;\; k = 4, \;\; \binom{9}{4} = 126 \geq 100 \;\Rightarrow\; \textbf{(A)}$$

💡 A construction beats a bound. Showing $9$ works and $8$ doesn't pins the minimum exactly at $9$.

[1] #16 7.SP.C.8 Translate the language condition into set language. Let $L_A$ be the set of lang

[2] #9 7.SP.C.8 Smaller case to see the structure. With $n$ languages available, the number of d

[3] #9 8.EE.A.1 Set up the search. We need the smallest $n$ such that $\binom{n}{k} \geq 100$ fo

[4] #6 7.SP.C.8 Guess and check $n = 7, 8, 9$. $\binom{7}{3} = 35 < 100$. $\binom{8}{4} = 70 < 1

[5] #9 7.SP.C.8 Verify the construction. With $n = 9$ languages and $k = 4$, pick any $100$ dist

Review

Reasonableness: The answer $9$ feels small for $100$ students, but $\binom{9}{4}=126$ — and the choose-function grows fast. Quick sanity: with $4$ languages each from a pool of $9$, two students' language lists can differ in even a single swap (swap one language for one not yet in the set) and still meet the condition, so the condition is generous, not restrictive. The other choices $10, 12, 51, 100$ would all over-shoot: $51$ would suggest "speak only your own language plus one of the other $50$", which over-counts; $100$ is the trivial upper bound "one language per student". The (A) answer captures the right combinatorial intuition.

Alternative: Tool #3 (Eliminate Possibilities): the inequality $\binom{n}{k} \geq 100$ rules out (B)-(E) only after we have shown $9$ suffices. A different elimination: any answer $n \geq 100$ is wasteful because $\binom{100}{1}=100$ trivially works; so the real question is just "how low can we drop $n$ before $\binom{n}{\lfloor n/2 \rfloor}$ falls below $100$". The threshold is the smallest $n$ for which the central binomial coefficient is $\geq 100$, and that is $n=9$ since $\binom{8}{4}=70 < 100 \leq 126 = \binom{9}{4}$.

CCSS standards used (min grade 8)

7.SP.C.8 Find probabilities of compound events using organized lists, tables, and simulation (Counting the number of distinct $k$-language subsets out of $n$ as $\binom{n}{k}$ — the combinatorial "organized list / compound event" idea that underlies Grade 7 probability counting.)
8.EE.A.1 Know and apply the properties of integer exponents (Recognizing that $\binom{n}{k}$ is maximized near $k = n/2$ (a property of binomial-coefficient growth, the same machinery behind $2^n = \sum_k \binom{n}{k}$).)

⭐ This AMC 10 problem only needs Grade 7 "counting subsets" combinatorics — $\binom{n}{k}$ — that you already know!

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: A

Review

CCSS standards used (min grade 8)

More like this