16. Let $f(x)=x^{2}-r_{2} x+r_{3}$ for all real numbers $x$, where $r_{2}$ and $r_{3}$ are some real numbers. Define a sequence $\left\{g_{n}\right\}$ for all nonnegative integers $n$ by $g_{0}=0$ and $g_{n+1}=f\left(g_{n}\right)$. Assume that $\left\{g_{n}\right\}$ satisfies the following three conditions: (i) $g_{2 i}g_{2 i+2}$ for all $0 \leq i \leq 2011$; (ii) there exists a positive integer $j$ such that $g_{i+1}>g_{i}$ for all $i>j$, and (iii) $\left\{g_{n}\right\}$ is unbounded. If $A$ is the greatest number such that $A \leq\left|r_{2}\right|$ for any function $f$ satisfying these properties, find $A$.
Answer: 2 Consider the function $f(x)-x$. By the constraints of the problem, $f(x)-x$ must be negative for some $x$, namely, for $x=g_{2 i+1}, 0 \leq i \leq 2011$. Since $f(x)-x$ is positive for $x$ of large absolute value, the graph of $f(x)-x$ crosses the $x$-axis twice and $f(x)-x$ has two real roots, say $ax>a$, while for $x>b, f(x)>x>b$. Let $c \neq b$ be the number such that $f(c)=f(b)=b$. Note that $b$ is not the vertex as $f(a)=ab$ then $xb$. Consider the smallest $j$ such that $g_{j}>b$. Then by the above observation, $g_{j-1}1$; in fact $j \geq 4025$.) Since $g_{j-1}=f\left(g_{j-2}\right)$, the minimum value of $f$ is less than $c$. The minimum value is the value of $f$ evaluated at its vertex, $\frac{b+a-1}{2}$, so
$$
\begin{aligned}
f\left(\frac{b+a-1}{2}\right) & 2$, but $b>a$, so the latter must hold and $(b-a)^{2}>9$. Now, the discriminant of $f(x)-x$ equals $(b-a)^{2}$ (the square of the difference of the two roots) and $\left(r_{2}+1\right)^{2}-4 r_{3}$ (from the coefficients), so $\left(r_{2}+1\right)^{2}>9+4 r_{3}$. But $r_{3}=g_{1}>g_{0}=0$ so $\left|r_{2}\right|>2$.
We claim that we can make $\left|r_{2}\right|$ arbitrarily close to 2 , so that the answer is 2 . First define $G_{i}, i \geq 0$ as follows. Let $N \geq 2012$ be an integer. For $\varepsilon>0$ let $h(x)=x^{2}-2-\varepsilon, g_{\varepsilon}(x)=-\sqrt{x+2+\varepsilon}$ and $G_{2 N+1}=2+\varepsilon$, and define $G_{i}$ recursively by $G_{i}=g_{\varepsilon}\left(G_{i+1}\right), G_{i+1}=h\left(G_{i}\right)$. (These two equations are consistent.) Note the following.
(i) $G_{2 i}G_{2 i+2}$ for $0 \leq i \leq N-1$. First note $G_{2 N}=-\sqrt{4+2 \varepsilon}>-\sqrt{4+2 \varepsilon+\varepsilon^{2}}=$ $-2-\varepsilon$. Let $l$ be the negative solution to $h(x)=x$. Note that $-2-\varepsilon0>G_{2 N}$. Now $g_{\varepsilon}(x)$ is defined as long as $x \geq-2-\varepsilon$, and it sends $(-2-\varepsilon, l)$ into $(l, 0)$ and $(l, 0)$ into $(-2-\varepsilon, l)$. It follows that the $G_{i}, 0 \leq i \leq 2 N$ are well-defined; moreover, $G_{2 i}l$ for $0 \leq i \leq N-1$ by backwards induction on $i$, so the desired inequalities follow.
(ii) $G_{i}$ is increasing for $i \geq 2 N+1$. Indeed, if $x \geq 2+\varepsilon$, then $x^{2}-x=x(x-1)>2+\varepsilon$ so $h(x)>x$. Hence $2+\varepsilon=G_{2 N+1}2+\varepsilon$, so $G_{i}$ increases faster and faster for $i \geq 2 N+1$.

Now define $f(x)=h\left(x+G_{0}\right)-G_{0}=x^{2}+2 G_{0} x+G_{0}^{2}-G_{0}-2-\varepsilon$. Note $G_{i+1}=h\left(G_{i}\right)$ while $g_{i+1}=f\left(g_{i}\right)=h\left(g_{i}+G_{0}\right)-G_{0}$, so by induction $g_{i}=G_{i}-G_{0}$. Since $\left\{G_{i}\right\}_{i=0}^{\infty}$ satisfies (i), (ii), and (iii), so does $g_{i}$.

We claim that we can make $G_{0}$ arbitrarily close to -1 by choosing $N$ large enough and $\varepsilon$ small enough; this will make $r_{2}=-2 G_{0}$ arbitrarily close to 2 . Choosing $N$ large corresponds to taking $G_{0}$ to be a larger iterate of $2+\varepsilon$ under $g_{\varepsilon}(x)$. By continuity of this function with respect to $x$ and $\varepsilon$, it suffices to
take $\varepsilon=0$ and show that (letting $g=g_{0}$ )
$$
g^{(n)}(2)=\underbrace{g(\cdots g}_{n}(2) \cdots) \rightarrow-1 \text { as } n \rightarrow \infty .
$$

But note that for $0 \leq \theta \leq \frac{\pi}{2}$,
$$
g(-2 \cos \theta)=-\sqrt{2-2 \cos \theta}=-2 \sin \left(\frac{\theta}{2}\right)=2 \cos \left(\frac{\pi}{2}-\frac{\theta}{2}\right) .
$$

Hence by induction, $g^{(n)}(-2 \cos \theta)=-2 \cos \left(\frac{\pi}{2}-\frac{\pi}{4}+\cdots+(-1)^{n}\left(\theta-\frac{\pi}{2^{n}}\right)\right)$. Hence $g^{(n)}(2)=g^{(n-1)}(-2 \cos 0)$ converges to $-2 \cos \left(\frac{\pi}{2}-\frac{\pi}{4}+\cdots\right)=-2 \cos \left(\frac{\pi}{3}\right)=-1$, as needed.