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 "2022 USAJMO Problems/Problem 1"

(→‎Solution 1: there is no point in having an incorrect solution in the wiki, let's wipe up this mess)
(→‎Solution 1)
Line 34: Line 34:
 
<math>m</math> satisfies the conditions precisely when <math>m</math> is not squarefree.
 
<math>m</math> satisfies the conditions precisely when <math>m</math> is not squarefree.
  
−
To begin, we let the common difference of <math>\{a_n\}</math> be <math>d</math> and the common ratio of <math>\{g_n\}</math> be <math>r</math>. Then, rewriting the conditions modulo <math>m</math> gives:
+
Consider three consecutive terms of the arithmetic sequence modulo <math>m</math>: <math>x - d</math>, <math>x</math>, and <math>x + d</math>. To satisfy the given conditions, the arithmetic and geometric sequences must match modulo <math>m</math>. Thus,
−
<cmath>a_2-a_1=d\not\equiv 0\pmod{m}\text{        (1)}</cmath>
+
<cmath>(x - d)(x + d) \equiv x^2 \pmod{m}</cmath>
−
<cmath>a_n\equiv g_n\pmod{m}\text{             (2)}</cmath>
+
which simplifies to
 +
<cmath>x^2 - d^2 \equiv x^2 \pmod{m} \implies d^2 \equiv 0 \pmod{m}.</cmath>
  
−
Condition <math>(1)</math> holds if no consecutive terms in <math>a_i</math> are equivalent modulo <math>m</math>, which is the same thing as never having consecutive, equal, terms, in <math>a_i\pmod{m}</math>. By Condition <math>(2)</math>, this is also the same as never having equal, consecutive, terms in <math>g_i\pmod{m}</math>:
+
If <math>m</math> is squarefree, the congruence <math>d^2 \equiv 0 \pmod{m}</math> implies <math>m \mid d</math>, forcing the arithmetic sequence to be constant modulo <math>m</math>, a contradiction. Thus, no solution exists for squarefree <math>m</math>.
  
−
<cmath>(1)\iff g_l\not\equiv g_{l-1}\pmod{m}\text{ for any integer }l>1</cmath>
+
Conversely, suppose <math>m</math> is divisible by some prime square <math>p^2</math>. Consider the arithmetic sequence
−
<cmath>\iff g_{l-1}(r-1)\not\equiv 0\pmod{m}.\text{        (3)}</cmath>
+
<cmath>1,\quad 1 + \frac{m}{p},\quad 1 + 2\frac{m}{p},\quad \dots</cmath>
−
 
+
and the geometric sequence
−
 
+
<cmath>1,\quad 1 + \frac{m}{p},\quad \left(1 + \frac{m}{p}\right)^2,\quad \dots</cmath>
−
Also, Condition <math>(2)</math> holds if
+
These sequences clearly satisfy the required conditions modulo <math>m</math>. Thus, solutions exist precisely when <math>m</math> is not squarefree.
−
<cmath>g_{l+1}-g_l\equiv g_l-g_{l-1}\pmod{m}</cmath>
 
−
<cmath>g_{l-1}(r-1)^2\equiv0\pmod{m}\text{       (4)}.</cmath>
 
−
 
 
−
Restating, <math>(1),(2)\quad \textrm{if} \quad(3),(4)</math>, and the conditions <math>g_{l-1}(r-1)\not\equiv 0\pmod{m}</math> and <math>g_{l-1}(r-1)^2\equiv0\pmod{m}</math> hold if and only if <math>m</math> is a perfect square.
 
  
 
==See Also==
 
==See Also==
 
{{USAJMO newbox|year=2022|before=First Question|num-a=2}}
 
{{USAJMO newbox|year=2022|before=First Question|num-a=2}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 00:02, 10 March 2025

Problem

For which positive integers $m$ does there exist an infinite arithmetic sequence of integers $a_1,a_2,\cdots$ and an infinite geometric sequence of integers $g_1,g_2,\cdots$ satisfying the following properties?

$\bullet$ $a_n-g_n$ is divisible by $m$ for all integers $n>1$;

$\bullet$ $a_2-a_1$ is not divisible by $m$.

Solution

Let the arithmetic sequence be $\{ a, a+d, a+2d, \dots \}$ and the geometric sequence to be $\{ g, gr, gr^2, \dots \}$. Rewriting the problem based on our new terminology, we want to find all positive integers $m$ such that there exist integers $a,d,r$ with $m \nmid d$ and $m|a+(n-1)d-gr^{n-1}$ for all integers $n>1$.

Note that \[m | a+nd-gr^n \; (1),\] \[m | a+(n+1)d-gr^{n+1} \; (2),\] \[m | a+(n+2)d-gr^{n+2} \; (3),\]

for all integers $n\ge 1$. From (1) and (2), we have $m | d-gr^{n+1}+gr^n$ and from (2) and (3), we have $m | d-gr^{n+2}+gr^{n+1}$. Reinterpreting both equations,

\[m | gr^{n+1}-gr^n-d \; (4),\] \[m | gr^{n+2}-gr^{n+1}-d \; (5),\]

for all integers $n\ge 1$. Thus, $m | gr^k - 2gr^{k+1} + gr^{k+2} = gr^k(r-1)^2 \; (6)$. Note that if $m|g,r$, then $m|gr^{n+1}-gr^n$, which, plugged into (4), yields $m|d$, which is invalid. Also, note that (4)$+$(5) gives

\[m | gr(r-1)(r+1) - 2d \; (7),\]

so if $r \equiv \pm 1 \pmod m$ or $gr \equiv 0 \pmod m$, then $m|d$, which is also invalid. Thus, according to (6), $m|g(r-1)^2$, with $m \nmid g,r$. Also from (7) is that $m \nmid g(r-1)$.

Finally, we can conclude that the only $m$ that will work are numbers in the form of $xy^2$, other than $1$, for integers $x,y$ ($x$ and $y$ can be equal), ie. $4,8,9,12,16,18,20,24,25,\dots$.

~sml1809

Solution 1

$m$ satisfies the conditions precisely when $m$ is not squarefree.

Consider three consecutive terms of the arithmetic sequence modulo $m$: $x - d$, $x$, and $x + d$. To satisfy the given conditions, the arithmetic and geometric sequences must match modulo $m$. Thus, \[(x - d)(x + d) \equiv x^2 \pmod{m}\] which simplifies to \[x^2 - d^2 \equiv x^2 \pmod{m} \implies d^2 \equiv 0 \pmod{m}.\]

If $m$ is squarefree, the congruence $d^2 \equiv 0 \pmod{m}$ implies $m \mid d$, forcing the arithmetic sequence to be constant modulo $m$, a contradiction. Thus, no solution exists for squarefree $m$.

Conversely, suppose $m$ is divisible by some prime square $p^2$. Consider the arithmetic sequence \[1,\quad 1 + \frac{m}{p},\quad 1 + 2\frac{m}{p},\quad \dots\] and the geometric sequence \[1,\quad 1 + \frac{m}{p},\quad \left(1 + \frac{m}{p}\right)^2,\quad \dots\] These sequences clearly satisfy the required conditions modulo $m$. Thus, solutions exist precisely when $m$ is not squarefree.

See Also

2022 USAJMO (Problems • Resources)
Preceded by
First Question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_USAJMO_Problems/Problem_1&oldid=244613"