2021 JMPSC Invitationals Problems/Problem 11

Revision as of 15:47, 11 July 2021 by Samrocksnature (talk | contribs) (Solution)

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