Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2021 JMPSC Invitationals Problems/Problem 11

Revision as of 14:49, 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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_JMPSC_Invitationals_Problems/Problem_11&oldid=157965"