Saudi Arabia Mathematical Competitions 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 _{\begin{array}{c}1\le x_1\le n\\ 1\le a\le n\end{array}}\frac{n}{a{x}_1}=n{\left(1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}\right)}^2.(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}+\cdots +\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.

---

Alternative solution.

Write $f(x)=a(x+x_1)(x+x_2)$, with $x_1,x_2\in {\mathbb{Z}}_{+}^{\ast }$. 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+nx+n-1)$, so we have $\left[\frac{n}{n}\right]$ solutions. Altogether, we have $$b_n=\sum _{k=2}^n\lfloor \frac{n}{k}\rfloor (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<\cdots <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}=\cdots =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 $$\lfloor \frac{\tau \left(\frac{c}{a}\right)-1}{2}\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{array}{rl}{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{array}(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.