Problem 6 · AMC 8 Stretch
Stretch
Number Theory
Counting & Probability
pigeonholeorganizing-data
Pick any 51 numbers from \(1, 2, 3, \dots, 100\). Show that two of them must have the property that one is a multiple of the other.
Show answer
Answer: one of the two is a multiple of the other
Show hints
Hint 1 of 4
When is one number a multiple of another? Doubling is a clue: \(6\) is a multiple of \(3\), and \(12\) is a multiple of both. Try grouping numbers linked by repeated doubling.
Still stuck? Show hint 2 →
Hint 2 of 4
Every whole number is an odd number times a power of 2 (its 'odd part'). Group the numbers 1 to 100 by their odd part — for example, odd part 3 gives \(\{3, 6, 12, 24, 48, 96\}\). How many different odd parts are possible?
Still stuck? Show hint 3 →
Hint 3 of 4
The odd parts are \(1, 3, 5, \dots, 99\) — exactly 50 of them. So there are 50 groups (boxes). You're picking 51 numbers.
Show solution
Approach: Pigeonhole on 'odd part' — 51 numbers, 50 odd parts
- Any whole number can be written as (an odd number) \(\times\) (a power of 2); call the odd factor its 'odd part'. For instance \(40 = 5\times 2^3\).
- Group the numbers 1 to 100 by odd part, e.g. \(\{1,2,4,8,16,32,64\}\), \(\{3,6,12,24,48,96\}\), \(\{5,10,20,40,80\}, \dots\). The possible odd parts are \(1,3,5,\dots,99\), which is 50, so there are 50 boxes.
- Drop your 51 chosen numbers into the 50 boxes. Since \(51 > 50\), two of them, say \(a < b\), share a box.
- In one box every number is a power of 2 times the same odd part, so \(b\) equals \(a\) times some power of 2 — making \(b\) a multiple of \(a\).
Mark:
· log in to save