Problem 25 · 2013 Math Kangaroo
Stretch
Number Theory
number-systems
Let \(f : \mathbb{N} \to \mathbb{N}\) be defined by \(f(n) = \frac{n}{2}\) for even n and \(f(n) = \frac{n-1}{2}\) for odd n. For a positive integer k, let \(f^{k}(n)\) mean applying f a total of k times. How many solutions does the equation \(f^{2013}(n) = 1\) have?
Show answer
Answer: D — \(2^{2013}\)
Show hints
Hint 1 of 2
For both even and odd n, the map is just the integer halving floor(n/2).
Still stuck? Show hint 2 →
Hint 2 of 2
Applying it k times gives floor(n / 2^k).
Show solution
Approach: iterate the halving map
- f(n) = floor(n/2) for every n, so f^2013(n) = floor(n / 2^2013).
- This equals 1 exactly when 2^2013 ≤ n < 2^2014.
- That interval holds 2^2013 integers, so D.
Mark:
· log in to save