Difference between revisions of "2022 USAJMO Problems/Problem 1"
Aidensharp (talk | contribs) |
Math-titan (talk | contribs) (→Solution 1) |
||
(12 intermediate revisions by 6 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 | + | 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> | ||
− | Condition <math>(1)</math> holds | + | 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>: |
<cmath>(1)\iff g_l\not\equiv g_{l-1}\pmod{m}\text{ for any integer }l>1</cmath> | <cmath>(1)\iff g_l\not\equiv g_{l-1}\pmod{m}\text{ for any integer }l>1</cmath> | ||
Line 20: | Line 44: | ||
− | Also, Condition <math>(2)</math> holds | + | Also, Condition <math>(2)</math> holds if |
<cmath>g_{l+1}-g_l\equiv g_l-g_{l-1}\pmod{m}</cmath> | <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> | <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. | |
[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== | ||
+ | {{USAJMO newbox|year=2022|before=First Question|num-a=2}} | ||
+ | {{MAA Notice}} |
Latest revision as of 01:05, 2 June 2024
Contents
Problem
For which positive integers does there exist an infinite arithmetic sequence of integers
and an infinite geometric sequence of integers
satisfying the following properties?
is divisible by
for all integers
;
is not divisible by
.
Solution
Let the arithmetic sequence be and the geometric sequence to be
. Rewriting the problem based on our new terminology, we want to find all positive integers
such that there exist integers
with
and
for all integers
.
Note that
for all integers . From (1) and (2), we have
and from (2) and (3), we have
. Reinterpreting both equations,
for all integers . Thus,
. Note that if
, then
, which, plugged into (4), yields
, which is invalid. Also, note that (4)
(5) gives
so if or
, then
, which is also invalid. Thus, according to (6),
, with
. Also from (7) is that
.
Finally, we can conclude that the only that will work are numbers in the form of
, other than
, for integers
(
and
can be equal), ie.
.
~sml1809
Solution 1
We claim that satisfies the given conditions if and only if
is a perfect square.
To begin, we let the common difference of be
and the common ratio of
be
. Then, rewriting the conditions modulo
gives:
Condition holds if no consecutive terms in
are equivalent modulo
, which is the same thing as never having consecutive, equal, terms, in
. By Condition
, this is also the same as never having equal, consecutive, terms in
:
Also, Condition holds if
Restating, , and the conditions
and
hold if and only if
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 then
or
is not divisble by
. If
, this is false and this is not possible. But if it isn't, if
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|, m has at most one of each prime factor of
, but then m has at most one of each prime factor of
, so m divides
, 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.