Problem 21 · AMC 8 Stretch
Stretch
Number Theory
Counting & Probability
pigeonholeorganizing-data
Pick any 7 numbers from \(1, 2, 3, \dots, 12\). Show that among them, one number is a multiple of another.
Show answer
Answer: one of two numbers is a multiple of the other
Show hints
Hint 1 of 4
Use the same 'odd part' idea as the 1-to-100 problem: every number is an odd number times a power of 2.
Still stuck? Show hint 2 →
Hint 2 of 4
Group the numbers 1 to 12 by their odd part. For example odd part 3 gives \(\{3, 6, 12\}\). The odd parts available are \(1, 3, 5, 7, 9, 11\).
Still stuck? Show hint 3 →
Hint 3 of 4
There are 6 odd numbers in 1–12, so 6 groups (boxes). You're picking 7 numbers.
Show solution
Approach: Pigeonhole on 'odd part' — 7 numbers, 6 odd parts
- Every number is (an odd number) \(\times\) (a power of 2). Group the numbers 1 to 12 by their odd part: \(\{1,2,4,8\}, \{3,6,12\}, \{5,10\}, \{7\}, \{9\}, \{11\}\).
- The odd parts are \(1,3,5,7,9,11\) — that's 6 groups, so 6 boxes.
- Pick your 7 numbers and drop them into the boxes. Since \(7 > 6\), two numbers \(a < b\) share an odd part.
- In one box every number is the same odd part times a power of 2, so \(b\) is \(a\) times a power of 2 — making \(b\) a multiple of \(a\).
Mark:
· log in to save