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

Difference between revisions of "2021 JMPSC Invitationals Problems/Problem 11"

(Created page with "==Problem== For some <math>n</math>, the arithmetic progression <cmath>4,9,14,\ldots,n</cmath> has exactly <math>36</math> perfect squares. Find the maximum possible value of...")
 
(→‎Solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
asdf
+
First note that the integers in the given arithmetic progression are precisely the integers which leave a remainder of <math>4</math> when divided by <math>5</math>.
 +
 
 +
Suppose a perfect square <math>m^2</math> is in this arithmetic progression.  Observe that the remainders when <math>0^2</math>, <math>1^2</math>, <math>2^2</math>, <math>3^2</math>, and <math>4^2</math> are divided by <math>5</math> are <math>0</math>, <math>1</math>, <math>4</math>, <math>4</math>, and <math>1</math>, respectively.  Furthermore, for any integer <math>m</math>, [(m+5)^2 = m^2 + 10m + 25 = m^2 + 5(2m + 5),] and so <math>(m+5)^2</math> and <math>m^2</math> leave the same remainder when divided by <math>5</math>.  It follows that the perfect squares in this arithmetic progression are exactly the numbers of the form <math>(5k+2)^2</math> and <math>(5k+3)^2</math>, 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 <math>k=1</math>, the third and fourth are associated with <math>k=2</math>, and so on.  It follows that the <math>37^{\text{th}}</math> such number, which is associated with <math>k=18</math>, is [(5\cdot 18 + 2)^2 = 92^2 = 9409.] Therefore the arithmetic progression must not reach <math>8464</math>.  This means the desired answer is <math>\boxed{8459}.</math> ~djmathman

Revision as of 14:47, 11 July 2021

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=157962"