2001 USA TST Problems/Problem 8


(Titu Andreescu) Find all pairs of nonnegative integers $(m, n)$ such that \[(m+n-5)^2 = 9mn.\]


All solutions are consecutive pairs of one of the sequences given recursively by \begin{align*} a_0 &= 0, \\ a_1 &= 5, \\ a_n &= \frac{(a_{n-1}-5)^2}{a_{n-2}} \end{align*} and \begin{align*} b_0 &= b_1 = 1, \\ b_n &= \frac{(b_{n-1}-5)^2}{b_{n-2}} . \end{align*}

Call a solution $(m,n)$ primitive if there is no solution $(m',n)$ with $m'<m$ and no solution $(m,n')$ with $n'<n$. Since the given equation is of degree 2, for any integer $n$, there exist at most two integers $m_1,m_2$ such that $(m_1,n)$ and $(m_2,n)$ are solutions; it follows that every solution is a pair of consecutive terms in a sequence in which the first two terms form a primitive solution, and any two consecutive terms constitute a solution.

Now, suppose $(m,n)$ is a primitive solution, with $m\ge n$. Rearranging the given equation, we see \[m^2 - (7n+10)m + (n-5)^2 = 0 ,\] so $m$ is the smaller of the two nonnegative integer roots of the polynomial \[P(t) = t^2 - (7n+10)t + (n-5)^2 ,\] for if one root of this polynomial is a nonnegative integer, then so is the other.

The other root is evidently $(n-5)^2/m$. It follows that $n \le m \le \lvert n-5 \rvert$. Therefore $n\le 2$. If $n=0$, then the only root of this polynomial is 5; if $n=1$, then the roots of this polynomial are 1 and 16; if $n=2$, then its roots are not integers. Therefore $(m,n)=(0,5)$ and $(m,n)=(1,1)$ are the only primitive solutions.

Now for any $n$, the roots of $P(t)$ are the values of $m$ for which $(m,n)$ are the given equation; and these two roots $m_1, m_2$ satisfy $m_1m_2 = (n-5)^2$. Hence the recursive relations given at the beginning of the problem give all solutions, as desired. We may note that the sequence $\{a_k\}, \{ b_k\}$ are the sequences $\{ 5F_{2k}^2 \}$ and $\{L_{2k-1}^2\}$, where $\{ F_k \}$ is the Fibonacci sequence and $\{ L_k \}$ is the Lucas sequence. $\blacksquare$

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


  • 2001 USA TST Problems
  • <url>Forum/viewtopic.php?t=24857 Discussion on AoPS/MathLinks</url>
  • <url>Forum/viewtopic.php?t=4999 Further discussion</url>