Problem 2 · AMC 8 Stretch
Core
Counting & Probability
Logic & Word Problems
pigeonholelogical-reasoning
At a party there are 6 people, and everyone knows at least one other person there. Show that at least 2 people know the exact same number of the others. (Knowing is mutual: if A knows B, then B knows A.)
Show answer
Answer: at least 2 people match
Show hints
Hint 1 of 4
Each person knows somewhere between 1 person (the smallest, since everyone knows at least one) and 5 people (everyone else).
Still stuck? Show hint 2 →
Hint 2 of 4
So each person's 'number of friends here' is one of the values 1, 2, 3, 4, or 5. How many choices is that?
Still stuck? Show hint 3 →
Hint 3 of 4
That's only 5 possible 'friend-count' labels, but there are 6 people. Make the 5 labels your boxes and drop each person into the box for their count.
Show solution
Approach: Pigeonhole — 6 people, only 5 possible friend-counts
- Each of the 6 people knows at least 1 other and at most 5 others, so each person's number of acquaintances is one of \(1, 2, 3, 4, 5\).
- That's only 5 possible values. Make those 5 values into 5 boxes ('knows 1', 'knows 2', ..., 'knows 5').
- Put each of the 6 people into the box for how many people they know. With 6 people and only 5 boxes, some box holds at least 2 people.
- Those 2 people know the same number of others, so at least \(2\) people must match.
Mark:
· log in to save