Competition problem — Algebra — Maths Olympiad Prep

Library / /18 of 71

Algebra Difficulty 4.9 AIME Prove it United States

Problem:
Let $f(n)$ be the number of times you have to hit the $\sqrt{\ }$ key on a calculator to get a number less than $2$ starting from $n$ . For instance, $f(2)=1$ , $f(5)=2$ . For how many $1 < m < 2008$ is $f(m)$ odd?

Solution

Solution:
Answer: $242$ This is $[2^{1}, 2^{2}) \cup [2^{4}, 2^{8}) \cup [2^{16}, 2^{32}) \ldots$ , and $2^{8} < 2008 < 2^{16}$ so we have exactly the first two intervals.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.