Problem 28 · 2020 Math Kangaroo
Stretch
Number Theory
divisibilityfactorization
Maria writes each positive divisor of 2020 on its own card and puts all the cards in a box. She then closes her eyes and draws the cards out one at a time. How many cards must she draw to be sure that among them are two numbers a and b with a not a divisor of b and b not a divisor of a?
Show answer
Answer: B — 6
Show hints
Hint 1 of 2
List the 12 divisors of 2020 and think of chains where each divides the next.
Still stuck? Show hint 2 →
Hint 2 of 2
A set with no 'incomparable' pair is just one such chain — how long can it be?
Show solution
Approach: longest divisibility chain plus one
- 2020 = 2²·5·101 has 12 divisors.
- A set with no incomparable pair is a chain under divisibility; the longest chain (for example 1, 2, 4, 404, 2020) has 5 elements.
- To be sure of an incomparable pair she must draw 5 + 1 = 6 cards.
Mark:
· log in to save