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 20:15, 11 July 2021 by Geometry285 (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

Solution 2

We examine all perfect squares ending in $4$ or $9$ are part of our sequence, so for every cycle of $10$ perfect squares, exactly $4$ are included. This means $9$ cycles are included, which goes until $90^2=8100$. Now, note $92^2=8464$ is not part of our sequence, but is the $37$th perfect square. Therefore, $5$ below this yields $\boxed{8459}$, which is the answer.

~Geometry285

Solution 3

Since $9-4=5,$ this arithmetic progression has common ratio 5. Thus, all terms in it are in the form $4+5n.$ Taking the modulo 5, all have either $1^2\equiv1\pmod5,2^2\equiv4\pmod5,3^2\equiv4\pmod5,4^2\equiv1\pmod5$ or $5^2\equiv0\pmod5.$ Thus all integers of the form $(2k+2)^2,(2k+3)^2$ are in the arithmetic progression and are perfect squares. This means that the 37 perfect square in the progression is $92^2.$ This also implies that the maximum value of $n$ is $92^2-5=\boxed{8459}$

~pinkpig

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

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