Problem 17 · AMC 8 Stretch
Core
Counting & Probability
Logic & Word Problems
pigeonholelogical-reasoning
In a town of 10 people, everyone has at least 1 friend (friendship is mutual). Show that at least 2 people have the same number of friends.
Show answer
Answer: at least 2 people have the same friend-count
Show hints
Hint 1 of 4
This is the party problem again. The people are the objects; their friend-count is the label.
Still stuck? Show hint 2 →
Hint 2 of 4
Each person has at least 1 friend and at most 9 friends (everyone else). List the possible friend-counts.
Still stuck? Show hint 3 →
Hint 3 of 4
The counts are \(1, 2, \dots, 9\) — that's 9 possible values (boxes) for 10 people.
Show solution
Approach: Pigeonhole — 10 people, only 9 possible friend-counts
- Each of the 10 people has at least 1 friend and at most 9 friends (everyone else in town), so each person's friend-count is one of \(1, 2, 3, \dots, 9\) — 9 possible values.
- Make these 9 values the boxes and put each person into the box equal to their number of friends.
- With 10 people but only 9 boxes, some box holds at least 2 people.
- Those two people have the same number of friends.
Mark:
· log in to save