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"

m (→‎Solution 1)
(→‎Solution 1)
 
(10 intermediate revisions by 4 users not shown)
Line 5: Line 5:
  
 
<math>\bullet</math> <math>a_2-a_1</math> is not divisible by <math>m</math>.
 
<math>\bullet</math> <math>a_2-a_1</math> is not divisible by <math>m</math>.
 +
 +
==Solution==
 +
 +
Let the arithmetic sequence be <math>\{ a, a+d, a+2d, \dots \}</math> and the geometric sequence to be <math>\{ g, gr, gr^2, \dots \}</math>. Rewriting the problem based on our new terminology, we want to find all positive integers <math>m</math> such that there exist integers <math>a,d,r</math> with <math>m \nmid d</math> and <math>m|a+(n-1)d-gr^{n-1}</math> for all integers <math>n>1</math>.
 +
 +
Note that
 +
<cmath>m | a+nd-gr^n \; (1),</cmath>
 +
<cmath>m | a+(n+1)d-gr^{n+1} \; (2),</cmath>
 +
<cmath>m | a+(n+2)d-gr^{n+2} \; (3),</cmath>
 +
 +
for all integers <math>n\ge 1</math>. From (1) and (2), we have <math>m | d-gr^{n+1}+gr^n</math> and from (2) and (3), we have <math>m | d-gr^{n+2}+gr^{n+1}</math>. Reinterpreting both equations,
 +
 +
<cmath>m | gr^{n+1}-gr^n-d \; (4),</cmath>
 +
<cmath>m | gr^{n+2}-gr^{n+1}-d \; (5),</cmath>
 +
 +
for all integers <math>n\ge 1</math>. Thus, <math>m | gr^k - 2gr^{k+1} + gr^{k+2} = gr^k(r-1)^2 \; (6)</math>. Note that if <math>m|g,r</math>, then <math>m|gr^{n+1}-gr^n</math>, which, plugged into (4), yields <math>m|d</math>, which is invalid. Also, note that (4)<math>+</math>(5) gives
 +
 +
<cmath>m | gr(r-1)(r+1) - 2d \; (7),</cmath>
 +
 +
so if <math>r \equiv \pm 1 \pmod m</math> or <math>gr \equiv 0 \pmod m</math>, then <math>m|d</math>, which is also invalid. Thus, according to (6), <math>m|g(r-1)^2</math>, with <math>m \nmid g,r</math>. Also from (7) is that <math>m \nmid g(r-1)</math>.
 +
 +
Finally, we can conclude that the only <math>m</math> that will work are numbers in the form of <math>xy^2</math>, other than <math>1</math>, for integers <math>x,y</math> (<math>x</math> and <math>y</math> can be equal), ie. <math>4,8,9,12,16,18,20,24,25,\dots </math>.
 +
 +
~sml1809
  
 
==Solution 1==
 
==Solution 1==
  
−
We claim that <math>m</math> satisfies the given conditions if and only if <math>m</math> is squareful.
+
We claim that <math>m</math> satisfies the given conditions if and only if <math>m</math> is a perfect square.
  
−
To begin, we let the common difference be <math>d</math> and the common ratio be <math>r</math>. Then, rewriting the conditions modulo <math>m</math> gives:
+
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:
 
<cmath>a_2-a_1=d\not\equiv 0\pmod{m}\text{        (1)}</cmath>
 
<cmath>a_2-a_1=d\not\equiv 0\pmod{m}\text{        (1)}</cmath>
 
<cmath>a_n\equiv g_n\pmod{m}\text{            (2)}</cmath>
 
<cmath>a_n\equiv g_n\pmod{m}\text{            (2)}</cmath>
Line 24: Line 48:
 
<cmath>g_{l-1}(r-1)^2\equiv0\pmod{m}\text{        (4)}.</cmath>
 
<cmath>g_{l-1}(r-1)^2\equiv0\pmod{m}\text{        (4)}.</cmath>
  
−
Whee! Restating, <math>(1),(2)\if (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 squareful.
+
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.
  
 
[will finish that step here]
 
[will finish that step here]
 +
 +
Note: This shouldn't work since we see that m = 12 is a solution. Let the initials for both series by 1, then let the ratio be 7 and the common difference to be 6. We see multiplying by 7 mod 12 that the geometric sequence is alternating from 1 to 7 to 1 to 7 and so on, which is the same as adding 6. Therefore, this solution is wrong. My counter-conjecture is that all non square-free m (4, 8, 9, 16, 18, 25...) should all work, but I don't have a proof. However, if you edit the one above, you can see non square-free m will work. In order to construct a ratio, we could us (4) and find a square multiple of m, take the square root and add 1 to get the ratio. Let <math>m = at^2</math> then <math>at + 1 \not\equiv 1 \pmod{at^2}</math> or <math>at</math> is not divisble by <math>at^2</math>. If <math>t = 1</math>, this is false and this is not possible. But if it isn't, if <math>m</math> isn't square free, then it should work.
 +
 +
Note: This counter-conjecture is correct. To prove it, it suffices to show that if m is square-free, then (3) and (4) contradict each other. Indeed, if m is square-free, then each prime dividing m only has a power of 1 in the prime factorization, so given (4) that m|<math>x\cdot (r-1)^2</math>, m has at most one of each prime factor of <math>x \cdot (r-1)^2</math>, but then m has at most one of each prime factor of <math>x \cdot (r-1)</math>, so m divides <math>x \cdot (r-1)</math>, contradicting (3).
  
 
==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}}

Latest revision as of 00:05, 2 June 2024

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

We claim that $m$ satisfies the given conditions if and only if $m$ is a perfect square.

To begin, we let the common difference of $\{a_n\}$ be $d$ and the common ratio of $\{g_n\}$ be $r$. Then, rewriting the conditions modulo $m$ gives: \[a_2-a_1=d\not\equiv 0\pmod{m}\text{ (1)}\] \[a_n\equiv g_n\pmod{m}\text{ (2)}\]

Condition $(1)$ holds if no consecutive terms in $a_i$ are equivalent modulo $m$, which is the same thing as never having consecutive, equal, terms, in $a_i\pmod{m}$. By Condition $(2)$, this is also the same as never having equal, consecutive, terms in $g_i\pmod{m}$:

\[(1)\iff g_l\not\equiv g_{l-1}\pmod{m}\text{ for any integer }l>1\] \[\iff g_{l-1}(r-1)\not\equiv 0\pmod{m}.\text{ (3)}\]


Also, Condition $(2)$ holds if \[g_{l+1}-g_l\equiv g_l-g_{l-1}\pmod{m}\] \[g_{l-1}(r-1)^2\equiv0\pmod{m}\text{ (4)}.\]

Restating, $(1),(2)\quad \textrm{if} \quad(3),(4)$, and the conditions $g_{l-1}(r-1)\not\equiv 0\pmod{m}$ and $g_{l-1}(r-1)^2\equiv0\pmod{m}$ hold if and only if $m$ is a perfect square.

[will finish that step here]

Note: This shouldn't work since we see that m = 12 is a solution. Let the initials for both series by 1, then let the ratio be 7 and the common difference to be 6. We see multiplying by 7 mod 12 that the geometric sequence is alternating from 1 to 7 to 1 to 7 and so on, which is the same as adding 6. Therefore, this solution is wrong. My counter-conjecture is that all non square-free m (4, 8, 9, 16, 18, 25...) should all work, but I don't have a proof. However, if you edit the one above, you can see non square-free m will work. In order to construct a ratio, we could us (4) and find a square multiple of m, take the square root and add 1 to get the ratio. Let $m = at^2$ then $at + 1 \not\equiv 1 \pmod{at^2}$ or $at$ is not divisble by $at^2$. If $t = 1$, this is false and this is not possible. But if it isn't, if $m$ isn't square free, then it should work.

Note: This counter-conjecture is correct. To prove it, it suffices to show that if m is square-free, then (3) and (4) contradict each other. Indeed, if m is square-free, then each prime dividing m only has a power of 1 in the prime factorization, so given (4) that m|$x\cdot (r-1)^2$, m has at most one of each prime factor of $x \cdot (r-1)^2$, but then m has at most one of each prime factor of $x \cdot (r-1)$, so m divides $x \cdot (r-1)$, contradicting (3).

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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