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

Latest revision as of 20:15, 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

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

@@ Line 15: / Line 15: @@
 Therefore the arithmetic progression must not reach <math>8464</math>.  This means the desired answer is <math>\boxed{8459}.</math> ~djmathman
+==Solution 2==
+We examine all perfect squares ending in <math>4</math> or <math>9</math> are part of our sequence, so for every cycle of <math>10</math> perfect squares, exactly <math>4</math> are included. This means <math>9</math> cycles are included, which goes until <math>90^2=8100</math>. Now, note <math>92^2=8464</math> is not part of our sequence, but is the <math>37</math>th perfect square. Therefore, <math>5</math> below this yields <math>\boxed{8459}</math>, which is the answer.
+~Geometry285
+==Solution 3==
+Since <math>9-4=5,</math> this arithmetic progression has common ratio 5. Thus, all terms in it are in the form <math>4+5n.</math> Taking the modulo 5, all have either <math>1^2\equiv1\pmod5,2^2\equiv4\pmod5,3^2\equiv4\pmod5,4^2\equiv1\pmod5</math> or <math>5^2\equiv0\pmod5.</math> Thus all integers of the form <math>(2k+2)^2,(2k+3)^2</math> are in the arithmetic progression and are perfect squares. This means that the 37 perfect square in the progression is <math>92^2.</math> This also implies that the maximum value of <math>n</math> is <math>92^2-5=\boxed{8459}</math>
+~pinkpig
 ==See also==

Page

Toolbox

Search