, 2012

The equations $x^2 + kx + k - 1 = 0$, $k = 2, \dots, n$, and $2x^2 + 4x + 2 = 0$, $x^2 + 4x + 4 = 0$, satisfy the property, hence $n+1 \le a_n$.
If $f$ is a quadratic function satisfying our property, then $f(x) = a(x + x_1)(x + x_2)$, where $x_1, x_2 \in \mathbb{Z}_+$, and $a, a(x_1 + x_2)$, $a x_1 x_2 \in \{1, 2, \dots, n\}$. From the last condition it follows that
$$x_2 \le \frac{n}{a x_1}.$$
We obtain
$$a_n \le \sum_{\substack{1 \le x_1 \le n \\ 1 \le a \le n}} \frac{n}{a x_1} = n \left( 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)^2. \quad (1)$$
It is easy to prove by induction that for every $n \ge 5$ the following inequality holds:
$$1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} < \sqrt{n}.$$
Moreover, $a_4 = 5$. Replacing in (1), we get $a_n < n^2$, $n \ge 5$, and the conclusion follows.

Write $f(x) = a(x + x_1)(x + x_2)$, with $x_1, x_2 \in \mathbb{Z}_+^*$. We have $b = a(x_1 + x_2)$, $c = a x_1 x_2$, and $c = a x_1 x_2 \le n$ implies $x_1, x_2 \in \{1, 2, \dots, n\}$.

First we count the quadratics with root $x_1 = 1$. If $x_2 = 1$, then $f(x) = a(x^2 + 2x + 1)$, so we have $\left[ \frac{n}{2} \right]$ solutions.
If $x_2 = 2$, then $f(x) = a(x^2 + 3x + 2)$, so we have $\left[ \frac{n}{3} \right]$ solutions.
......
If $x_2 = n - 1$, then $f(x) = a(x^2 + n x + n - 1)$, so we have $\left[ \frac{n}{n} \right]$ solutions.
Altogether, we have
$$b_n = \sum_{k=2}^n \left\lfloor \frac{n}{k} \right\rfloor \quad (1)$$
quadratics that have a root 1.

Let us now count the quadratics with both roots $x_1, x_2 \ge 2$. We have $b = a(x_1 + x_2) \le a x_1 x_1 = c \le n$. For any pair $(a, c)$, we want to count how many choices of $b$ there are. The only condition is that $b = a(x_1 + x_2)$, where $x_1 x_2 = \frac{c}{a} > 1$, and $x_1, x_2 \ge 2$ (since we have already proved that $0 < b \le c \le n$). Write the set of divisors of $\frac{c}{a}$ as
$$1 = d_1 < d_2 < \dots < d_{\tau(\frac{c}{a})} = \frac{c}{a}.$$
The pairs $d_1 d_{\tau(\frac{c}{a})} = d_2 d_{\tau(\frac{c}{a})-1} = \dots = d_{\tau(\frac{c}{a})} d_1$ are the solutions of $x_1 x_2 = \frac{c}{a}$. There are $\tau(\frac{c}{a})$ such pairs. Since
$$d_1 d_{\tau(\frac{c}{a})} = 1 \cdot \frac{c}{a} = \frac{c}{a} \cdot 1 = d_{\tau(\frac{c}{a})} d_1,$$
these two pairs are not acceptable (we assumed $x_1, x_2 \ne 1$). Now, any two symmetric pairs $d_m d_{\tau(\frac{c}{a})-m} = d_{\tau(\frac{c}{a})-m} d_m$ yield a unique value of the sum $d_m + d_{\tau(\frac{c}{a})-m}$, which gives a unique value of $b$.

There is an even number of divisors of $\frac{c}{a}$, unless $\frac{c}{a}$ is a square. So, if $\frac{c}{a}$ is not a square, we get $\frac{1}{2}(\tau(\frac{c}{a}) - 2)$ different sum $d_{\tau(\frac{c}{a})-m} + d_m$, with $m \in \{2, \dots, \tau(\frac{c}{a}) - 1\}$. If $\frac{c}{a}$ is a square, its pairs of divisors have $\frac{1}{2}(\tau(\frac{c}{a}) - 1)$ different sums (disconsidering pairs that contain 1). A unified formula for these results is
$$\left\lfloor \frac{\tau\left(\frac{c}{a}\right) - 1}{2} \right\rfloor.$$
Now we have established that for each pair
$$(a, c) \in \{1, \dots, n\} \times \{1, \dots, n\}$$
with $a|c$, there exist $\left[ \frac{\tau\left(\frac{c}{a}\right) - 1}{2} \right]$ quadratics which do not have a root 1, and for which $b \le n$.

Now we count the quadratics by taking the values of $\frac{c}{a}$ into account.
For $\frac{c}{a} = 2$, we can choose
$$(a, c) \in \left\{ (1, 2), (2, 4), \dots, \left( \left[ \frac{n}{2} \right], 2 \left[ \frac{n}{2} \right] \right) \right\},$$
hence we have $\left[ \frac{n}{2} \right] \left[ \frac{\tau(2) - 1}{2} \right]$ quadratics.
Generally, for $\frac{c}{a} = k$, we can choose $(a, c)$ from the set
$$\left\{ (1, k), (2, 2k), \dots, \left( \left[ \frac{n}{k} \right], k \left[ \frac{n}{k} \right] \right) \right\}.$$
hence we have $\left[ \frac{n}{k} \right] \left[ \frac{\tau(k) - 1}{2} \right]$ quadratics.
Altogether, we obtain the following exact formula for $a_n$
$$\begin{aligned} a_n = b_n + \sum_{k=2}^n \left[ \frac{n}{k} \right] \left[ \frac{\tau(k) - 1}{2} \right] &= \sum_{k=2}^n \left[ \frac{n}{k} \right] \left( \left[ \frac{\tau(k) - 1}{2} \right] + 1 \right) \\ &= \sum_{k=2}^n \left[ \frac{n}{k} \right] \left[ \frac{\tau(k) + 1}{2} \right]. \end{aligned} \quad (2)$$
From (2) we obtain
$$a_n \le n \sum_{k=2}^n \frac{\tau(k) + 1}{2k} \le n \sum_{k=2}^n \frac{2\sqrt{k} + 1}{2k}$$
$$= n \sum_{k=2}^n \frac{1}{\sqrt{k}} + \frac{n}{2} \sum_{k=2}^n \frac{1}{k}$$
$$\le n(2\sqrt{n+1} - 1) + \frac{n}{2}(\ln(n+1) + C - 1) < n^2,$$
where $C$ is the well-known Euler's constant.