Difference between revisions of "2024 AMC 10B Problems/Problem 12"

Latest revision as of 13:02, 22 September 2025

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$

Solution 1 (Pure Logic)

We think of this problem like boxes. First start with 9. We see that we can arrange the groups of people into the 9 boxes. We take 9 people of different languages and arrange them in each of the boxes. This means we have $ 100 - 9 \times 9 = 19 $ people remaining. We then take 18 people of different language (as they can be put in a pair and still qualify) and put them in the boxes. This gives us 1 person left over. Now, this is where MAA wants you to choose 10, but one can quickly see that the last person can be put into any group of three (except a group that includes their language) and still qualify whilst maintaining all the constraints. Therefore our answer is $\boxed{9}$ .

This solution is a basic introduction/summary of the Pigeonhole Principle

~Pinotation

Solution 2

Let's say we have some number of languages. Then each student will speak some amount of those languages, and no two people can have the same combination of languages or else the conditions will no longer be satisfied. Notice that $\dbinom94=126\geq100$ . So each of the $100$ students can speak some $4$ of the $9$ languages. Thus, $\boxed{9}$ is our answer.

~lprado ~LaTeX edits by Elephant200

Solution 3 (Rigorous)

Let $n$ be the total number of languages spoken by all the students, and let $k$ be the number of languages that each student speaks. Since all students speak the same number of languages, the condition given in the question can be modified as -

"If $N$ is the $n$ -element subset containing the union of the languages spoken by all students, each of the 100 students speaks a different (unique) $k$ -element subset of $N$ combination of languages."

In more mathematical terms, this means ${n \choose k} \ge 100$ . (Using PHP)

Because we need the least value of $n$ , $k$ must be the closest integer to $\frac{n}{2}$

$\Rightarrow {n \choose \frac{n}{2}} \ge 100$ for $n = 2m$ , ${n \choose \frac{n-1}{2}} \ge 100$ for $n=2m-1$ , $m \in \mathbb{N}$

In the context of this question, it will be fastest to just substitute $\normalsize n$ to each of the option values to find the least value possible as $\boxed{\textbf{(A) } 9}$

For a more rigorous proof, where options are not an option, one can manually count up from $n=1$ as $100$ is a small number.

~laythe_enjoyer211

Video Solution 1 by Pi Academy (Fast and Easy ⚡🚀)

https://youtu.be/YqKmvSR1Ckk?feature=shared

~ Pi Academy

Video Solution 2 by SpreadTheMathLove

https://www.youtube.com/watch?v=N46YcQPc4ro&t=0s

@@ Line 8: / Line 8: @@
 <math>\textbf{(A) } 9 \qquad\textbf{(B) } 10 \qquad\textbf{(C) } 12 \qquad\textbf{(D) } 51 \qquad\textbf{(E) } 100</math>
-==Solution 1==
+==Solution 1 (Pure Logic)==
-Let's say we have some number of languages. Then each student will speak some amount of those languages, and no two people can have the same combination of languages or else the conditions will no longer be satisfied. Notice that <math>{9}\choose{4}</math> <math>= 126 \geq 100</math>. So each of the <math>100</math> students can speak some <math>4</math> of the <math>9</math> languages. Thus, <math>\boxed{9}</math> is our answer.
+We think of this problem like boxes. First start with 9. We see that we can arrange the groups of people into the 9 boxes. We take 9 people of different languages and arrange them in each of the boxes. This means we have \( 100 - 9 \times 9 = 19 \) people remaining. We then take 18 people of different language (as they can be put in a pair and still qualify) and put them in the boxes. This gives us 1 person left over. Now, this is where MAA wants you to choose 10, but one can quickly see that the last person can be put into any group of three (except a group that includes their language) and still qualify whilst maintaining all the constraints. Therefore our answer is <math>\boxed{9}</math>.
+This solution is a basic introduction/summary of the [[Pigeonhole Principle]]
+~Pinotation
+==Solution 2==
+Let's say we have some number of languages. Then each student will speak some amount of those languages, and no two people can have the same combination of languages or else the conditions will no longer be satisfied. Notice that <math>\dbinom94=126\geq100</math>. So each of the <math>100</math> students can speak some <math>4</math> of the <math>9</math> languages. Thus, <math>\boxed{9}</math> is our answer.
 ~lprado
+~LaTeX edits by Elephant200
-==Solution 2 (Rigorous)==
+==Solution 3 (Rigorous)==
 Let <math>n</math> be the total number of languages spoken by all the students, and let <math>k</math> be the number of languages that each student speaks.
 Since all students speak the same number of languages, the condition given in the question can be modified as -
@@ Line 36: / Line 45: @@
 ~ Pi Academy
+==Video Solution 2 by SpreadTheMathLove==
+https://www.youtube.com/watch?v=N46YcQPc4ro&t=0s
 ==See also==
 {{AMC10 box|year=2024|ab=B|num-b=11|num-a=13}}
 {{MAA Notice}}

2024 AMC 10B (Problems • Answer Key • Resources)
Preceded by Problem 11	Followed by Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

Page

Toolbox

Search