C1 Let $F$ be a function which maps integers to integers by the following rules:
$F(n)=n-3$ if $n \geq 1000$;
$F(n)=F(F(n+5))$ if $n<1000$.
(a) Find $F(999)$.
(b) Show that $F(984)=F(F(F(1004)))$.
(c) Find $F(84)$.
(a) Answer: 998
(a) Solution: We must apply the second rule, since $999<1000$. We have that $F(999)=$ $F(F(1004))$. Now, we can apply the first rule, to reduce this to $F(1001)$. Applying the first rule again gives us the result of 998 .
$$
F(999)=F(F(1004))=F(1001)=998 \text {. }
$$
(b) Solution 1: By direct evaluation, applying the second rule four times we have
$$
F(984)=F(F(989))=F(F(F(994)))=F(F(F(F(999))))=F(F(F(F(F(1004))))) \text {. }
$$

Now, applying the first rule twice, then the second rule, we obtain $F(F(F(F(F(1004)))))=(F(F(F(F(1001))))=(F(F(F(998)))=(F(F(F(F(1003))))$.

Now, applying the first rule twice, then the second rule, the first and the second we get $(F(F(F(F(1003))))=(F(F(F(1000))))=F(F(997))=F(F(F(1002)))=F(F(999))=$ $F(F(F(1004)))$.

Thus, $F(984)=F(F(F(1004)))$.
(b) Solution 2: For this and the next part, we try to write down a table of values for the function $F$. When $n \geq 1000, F(n)=n-3$ is known, and in the previous part, we showed that $F(999)=998$. Now,
$$
\begin{array}{c}
F(998)=F(F(1003))=F(1000)=997, \\
F(997)=F(F(1002))=F(999)=998,
\end{array}
$$
and
$$
F(996)=F(F(1001))=F(998)=997 .
$$

We see that for $996 \leq n \leq 1001$ the results alternate between 998 and 997 , namely $F(n)=997$ if $n$ is even, and $F(n)=998$ if $n$ is odd. We can prove this for $n \leq 995$ by mathematical induction.

Let $k \leq 995$. Assume that for all $k+1 \leq n \leq 1001$, we have that
$$
F(n)=\left\{\begin{array}{ll}
997 & \text { if } n \text { is even, } \\
998 & \text { if } n \text { is odd }
\end{array} .\right.
$$

Then, we have
$$
F(k)=F(F(k+5))=\left\{\begin{array}{ll}
F(998)=997 & \text { if } k \text { is even, } \\
F(997)=998 & \text { if } k \text { is odd }
\end{array} .\right.
$$
(Here we use that $k+5$ is odd if $k$ is even and $k+5$ is even if $k$ is odd.)
This shows that $F(k)$ satisfies the same pattern, which completes the induction.
Equipped with our formula for $F$, we see that $F(984)=997$ and $F(F(F(1004)))=F(F(1001))$ $F(998)=997$, as desired.
(c) Answer: 997
(c) Solution 1: By the formula proved above in Solution 2 for (b), we have $F(84)=997$ (as 84 is even).
(c) Solution 2: By doing (a) we realize that $F^{n}(999)=F^{n-2}(999)$ for $n \geq 3$.

Here $F^{n}(x)=F(F(F \ldots F(x)))$, where $F$ occurs $n$ times, e.g. $F^{2}(x)=F(F(x))$. Specifically,
$$
F^{3}(999)=F^{4}(1004)=F^{2}(998)=F^{3}(1003)=F(997)=F^{2}(1002)=F(999) .
$$

Then $F(84)=F^{184}(84+5 * 183)=F^{184}(999)=F^{2}(999)=F(998)=997$.
P.S. One can similarly use 1004 instead of 999 . Since $F^{n}(1004)=F^{n-2}(1004)$ for $n \geq 3$ :
$$
F(84)=F^{185}(84+5 * 184)=F^{185}(1004)=F^{3}(1004)=F^{2}(1001)=F(998)=997 .
$$