AMC 10 · 2024 · #12

Grade 8 arithmetic

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

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

📏 Medium solution 💡 3 insights

Problem

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.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

100

AMC 10 2024 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Solve an Easier Related Problem

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 C(2, 1) = 2 distinct students; with n=3, at most C(3, 1) = 3 or C(3, 2) = 3. The pattern is "max students = C(n, k)". Tool #6 (Guess and Check) then walks n = 7, 8, 9 to find where C(n, k) first reaches 100 — pick k near $\frac{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.

1STEP 1

Turn words into sets: with equal size k, "neither list inside the other" just means the two language sets are different.

|L_A| = |L_B| = k and L_A ≠ L_B ⟺ condition holds

2STEP 2

Shrink to tiny cases: n languages give exactly C(n, k) distinct k-subsets, so the group size can be at most C(n, k).

#students ≤ C(n, k)

3STEP 3

Aim the search: want the smallest n with C(n, k) ≥ 100; since C(n, k) peaks at k near $\frac{n}{2}$ , only the middle value matters.

min { n : max_k C(n, k) ≥ 100 }

4STEP 4

Guess and check: C(7, 3) = 35 and C(8, 4) = 70 fall short, but C(9, 4) = 126 ≥ 100 clears it — first at n = 9, k = 4.

C(7, 3)=35, C(8, 4)=70, C(9, 4)=126

5STEP 5

Build it: assign each student a distinct 4-set from 9 languages — 126 exist, all same size, so none nest and condition holds. Least is 9.

n = 9, k = 4, C(9, 4) = 126 ≥ 100 → (A)

Answer

The answer 9 feels small for 100 students, but C(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.

💡Key takeaway

This AMC 10 problem only needs Grade 7 "counting subsets" combinatorics — C(n, k) — that you already know!

More like this