Problem 25 · 2015 Math Kangaroo
Hard
Number Theory
number-systemscareful-counting
How many three-digit whole numbers can be written as the sum of exactly nine different powers of two? (Hint: powers of two are 20, 21, 22, 23, …)
Show answer
Answer: E — 5
Show hints
Hint 1 of 2
A sum of nine different powers of two is a number with exactly nine 1's in binary.
Still stuck? Show hint 2 →
Hint 2 of 2
Keep the value between 100 and 999 — only the bottom ten bits are available.
Show solution
Approach: count numbers with exactly nine binary 1's in 100..999
- Such a number has exactly nine 1-bits; to stay under 1000 it can only use bits 0 through 9 (ten positions).
- Choosing nine of those ten bits means leaving one bit out: 1023 − 2^b.
- This is a 3-digit number for b = 5,6,7,8,9 (values 991,959,895,767,511) — exactly 5 numbers (E).
Mark:
· log in to save