1. Naomi has a broken calculator. All it can do is either add one to the previous answer, or square the previous answer. (It performs the operations correctly.) Naomi starts with 2 on the screen. In how many ways can she obtain an answer of 1000 ?
Solution 1
Let the notation $a \rightsquigarrow b$ mean "keep adding 1 to $a$ until you reach $b$ " (where $b \geq a$ ), and $a \leftrightarrow b$ mean "square $a$ to get $b$ ".

For example, one route to 1000 is $2 \leadsto 5 \leftrightarrow 25 \leadsto 30 \leftrightarrow 900 \leadsto 1000$.
Note that $31^{2}=9611000$.
If she does not square any numbers then there is one way to obtain 1000: $2 \leadsto 1000$.
If she squares a number once then her route to 1000 looks like this:
$$
2 \leadsto n \rightarrow n^{2} \leadsto 1000 \text {. }
$$

It is clear that $n$ can be any number with $n \geq 2$ and $n^{2} \leq 1000$, so $n \leq 31$, that is, $n$ can take any value from 2 to 31 inclusive.

There are therefore $\mathbf{3 0}$ ways she can obtain 1000 if she squares once.
If she squares a number twice then her route to 1000 looks like this:
$$
2 \rightsquigarrow a \leftrightarrow a^{2} \rightsquigarrow b \leftrightarrow b^{2} \rightsquigarrow 1000 \text {, }
$$
with $2 \leq a1000$. Hence $f(1000)=f(961)$.
Starting from $n=2$, we have, for the first few $n$ :
$$
f(2)=1, f(3)=1, f(4)=2, f(5)=2, \ldots f(8)=2, f(9)=3 .
$$

It is immediately apparent that, as the value of $n$ increases, $f(n)$ changes value only when $n$ is square.
So we have $f$ (everything from 9 up to 15 ) $=3$, then $f(16)=3+f(4)=3+2=5$.
For every square reached between 25 and 64 (inclusive) [of which there are 4], $f(n)$ increases by 2 (since $f(n)=2$ for $5 \leq n \leq 8$ ).
Then, as the value of $n$ increases:
for every square between 81 and 225 [7 squares], $f(n)$ increases by 3 (since $f(n)=3$ for $9 \leq n \leq 15)$
for every square between 256 and 576 [9 squares], $f(n)$ increases by 5 (since $f(n)=5$ for $16 \leq n \leq 24)$
for every square between 625 and 961 [7 squares], $f(n)$ increases by 7 (since $f(n)=7$ for $25 \leq n \leq 31)$;
So $f(1000)=f(961)=f(16)+2 \times 4+3 \times 7+5 \times 9+7 \times 7=\mathbf{1 2 8}$.