2021 JMPSC Invitationals Problems/Problem 11

Problem

For some $n$, the arithmetic progression \[4,9,14,\ldots,n\] has exactly $36$ perfect squares. Find the maximum possible value of $n.$

Solution

First note that the integers in the given arithmetic progression are precisely the integers which leave a remainder of $4$ when divided by $5$.


Suppose a perfect square $m^2$ is in this arithmetic progression. Observe that the remainders when $0^2$, $1^2$, $2^2$, $3^2$, and $4^2$ are divided by $5$ are $0$, $1$, $4$, $4$, and $1$, respectively. Furthermore, for any integer $m$, \[(m+5)^2 = m^2 + 10m + 25 = m^2 + 5(2m + 5),\] and so $(m+5)^2$ and $m^2$ leave the same remainder when divided by $5$. It follows that the perfect squares in this arithmetic progression are exactly the numbers of the form $(5k+2)^2$ and $(5k+3)^2$, respectively.


Finally, the sequence of such squares is \[(5\cdot 0 + 2)^2, (5\cdot 0 + 3)^2, (5\cdot 1 + 2)^2, (5\cdot 1 + 3)^2,\cdots.\]

In particular, the first and second such squares are associated with $k=1$, the third and fourth are associated with $k=2$, and so on. It follows that the $37^{\text{th}}$ such number, which is associated with $k=18$, is \[(5\cdot 18 + 2)^2 = 92^2 = 9409.\]

Therefore the arithmetic progression must not reach $8464$. This means the desired answer is $\boxed{8459}.$ ~djmathman


See also

  1. Other 2021 JMPSC Invitationals Problems
  2. 2021 JMPSC Invitationals Answer Key
  3. All JMPSC Problems and Solutions

The problems on this page are copyrighted by the Junior Mathematicians' Problem Solving Competition. JMPSC.png