C4. Let $f(x)=x^{2}-a x+b$, where $a$ and $b$ are positive integers.
(a) Suppose $a=2$ and $b=2$. Determine the set of real roots of $f(x)-x$, and the set of real roots of $f(f(x))-x$.
(b) Determine the number of pairs of positive integers $(a, b)$ with $1 \leq a, b \leq 2011$ for which every root of $f(f(x))-x$ is an integer.
Solution:
(a) If $a=2$ and $b=2$, then $f(x)=x^{2}-2 x+2$. Hence, $f(x)-x=x^{2}-3 x+2=(x-2)(x-1)$. Therefore, the roots of $f(x)-x$ are 1 and 2 .

We now determine $f(f(x))-x$. Note that $f(f(x))=\left(x^{2}-2 x+2\right)^{2}-2\left(x^{2}-2 x+2\right)+2=$ $x^{4}-4 x^{3}+6 x^{2}-4 x+2$. Therefore,
$$
f(f(x))-x=x^{4}-4 x^{3}+6 x^{2}-5 x+2 .
$$

Note that 1 is a root of $f(f(x))-x$. Then
$$
x^{4}-4 x^{3}+6 x^{2}-5 x+2=(x-1)\left(x^{3}-3 x^{2}+3 x-2\right)=(x-1)(x-2)\left(x^{2}-x+1\right) .
$$

Note that $x^{2}-x+1$ has no real roots since its discriminant is $1^{2}-4 \cdot 1 \cdot 1=-3<0$. Therefore, the real roots of $f(f(x))-x$ are 1 and 2 .
(b) The answer is 43 .

First, we claim that if $r$ is a root of $f(x)-x$, then $r$ is a root of $f(f(x))-x$. Since $r$ is a root of $f(x)-x, f(r)-r=0$, i.e. $f(r)=r$. Therefore,
$$
f(f(r))-r=f(r)-r=0 .
$$

Hence, any root of $f(x)-x$ is a root of $f(f(x))-x$. Consequently, $f(x)-x$ is a factor of $f(f(x))-x$.

Note that $f(f(x))-x=f\left(x^{2}-a x+b\right)-x=\left(x^{2}-a x+b\right)^{2}-a\left(x^{2}-a x+b\right)+b-x$,
$$
=x^{4}-2 a x^{3}+\left(a^{2}+2 b-a\right) x^{2}-\left(2 a b-a^{2}+1\right) x+\left(b^{2}-a b+b\right) \text {. }
$$

Since $f(x)-x=x^{2}-(a+1) x+b, f(f(x))-x$ factors as
$$
f(f(x))-x=\left(x^{2}-(a+1) x+b\right)\left(x^{2}-(a-1) x+(b-a+1)\right) .
$$

Since both factors are monic, every root of $f(f(x))-x$ is an integer if and only if the discriminants of both of these quadratic factors are perfect squares. These two discriminants are
$$
(a+1)^{2}-4 b=a^{2}+2 a+1-4 b
$$
and
$$
(a-1)^{2}-4(b-a+1)=a^{2}+2 a+1-4 b-4 .
$$

The first discriminant is four larger than the second discriminant. The only two perfect squares that differ by 4 are 4 and 0 . This statement is true since if $r, s$ are non-negative integers such that $r^{2}-s^{2}=4$, then $(r-s)(r+s)=4$. Since $r, s$ are non-negative, $(r-s, r+s)=(2,2)$ or (1,4). In the latter case, $r-s=1$ and $r+s=4$. Therefore, $r=5 / 2$ and $s=3 / 2$, which are not integers. Therefore, $(r-s, r+s)=(2,2)$, i.e. $r=2, s=0$. Hence, the larger perfect square is $2^{2}=4$ and the smaller perfect square is 0 .

Therefore, $a^{2}+2 a+1-4 b=4$. Rearranging this and factoring yields
$$
(a+1)^{2}=4(b+1) .
$$

Since $(a+1)^{2}$ and 4 are perfect squares, $b+1$ is a perfect square. Therefore, there exists a positive integer $m$ such that $b+1=m^{2}$. Then $b=m^{2}-1$. Consequently, $(a+1)^{2}=4 m^{2}$. Since $a$ is a positive integer, $a+1=2 m$. Hence, $a=2 m-1$. Therefore, $(a, b)=\left(2 m-1, m^{2}-1\right)$.

We now verify that all such $(a, b)$ have the property that the roots of $x^{2}-(a+1) x+b$ and $x^{2}-(a-1) x+(b-a+1)$ are all integers, implying that every root of $f(f(x))-x$ is an integer. Substituting $(a, b)=\left(2 m-1, m^{2}-1\right)$ into these two polynomials yield $x^{2}-2 m x+m^{2}-1=$ $(x-(m-1))(x-(m+1))$ and $x^{2}-(2 m-2) x+\left(m^{2}-2 m+1\right)=(x-(m-1))(x-(m-1))$. Since $\mathrm{m}$ is a positive integer, all four roots of $f(f(x))-x$ is an integer. (Alternately, note that since the leading coefficient of each of the quadratic factors is 1 , the roots of the quadratic factors are all integers if and only if the discriminant of the quadratic factors are both perfect square.)

Since $1 \leq a, b \leq 2011$, it remains to find the number of positive integers $m$ such that $1 \leq 2 m-1, m^{2}-1 \leq 2011$. Since $1 \leq m^{2}-1 \leq 2011,2 \leq m^{2} \leq 2012$. Hence, $2 \leq m \leq\lfloor\sqrt{2012}\rfloor=44$, where $\lfloor t\rfloor$ denotes the largest integer less than or equal to $t$. There are 43 solutions for $m$, namely $m=2,3, \ldots 44$. These values of $m$ clearly satisfy $1 \leq 2 m-1 \leq 2011$.

Therefore, the number of ordered positive integer pairs $(a, b)$ that results in $f(f(x))-x$ having all integer roots is 43 .