Problem 19 · 2013 Math Kangaroo
Medium
Counting & Probability
careful-counting
A box holds 900 cards numbered from 100 to 999, every number appearing once. Franz picks some cards and works out the digit sum on each. What is the minimum number of cards he must pick to be sure of having at least three with the same digit sum?
Show answer
Answer: C — 53
Show hints
Hint 1 of 2
First find how many different digit-sums the numbers 100–999 can have.
Still stuck? Show hint 2 →
Hint 2 of 2
Watch the extreme sums — some occur for only one card.
Show solution
Approach: pigeonhole with limited boxes
- Digit sums run 1 to 27, but sum 1 (100) and sum 27 (999) each occur only once.
- Worst case: 2 cards from each of the 25 sums 2–26 plus the two lone cards = 52 with no triple.
- The 53rd card forces a third of some sum, so the minimum is 53 = C.
Mark:
· log in to save