Problem 19 · AMC 8 Stretch
Core
Logic & Word Problems
Counting & Probability
pigeonholecounterexamplelogical-reasoning
Someone claims: 'If there are more leaves than trees, then at least 2 trees must have the same number of leaves.' Is this true? Explain.
Show answer
Answer: No — it is not always true
Show hints
Hint 1 of 4
Try the obvious pigeonhole setup, then test it on a tiny example to see if it really works.
Still stuck? Show hint 2 →
Hint 2 of 4
If trees are the boxes and leaves are the objects, pigeonhole says some tree has lots of leaves — but does it say two trees MATCH?
Still stuck? Show hint 3 →
Hint 3 of 4
Could one tree have 0 leaves? In the 'friends' problems, the trick worked because everyone had at LEAST 1. Here there's no such rule.
Show solution
Approach: Counterexample — pigeonhole forces a big count, not a tie
- The claim is NOT true in general. More leaves than trees only forces some tree to have several leaves; it does not force two trees to have the EXACT SAME count.
- Counterexample: 2 trees and 3 leaves (more leaves than trees). Give one tree 0 leaves and the other 3 leaves — more leaves than trees, yet the two counts differ.
- Why did the 'friends' problems work but this doesn't? There, everyone had at least 1 friend, squeezing the counts into the \(N-1\) values \(1, \dots, N-1\) — one fewer box than people. Here 0 leaves is allowed, so the counts aren't squeezed and the trick fails.
- So the answer is No.
Mark:
· log in to save