Difference between revisions of "2022 USAJMO Problems/Problem 1"

Revision as of 20:46, 5 April 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 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 why this makes sense.

@@ Line 28: / Line 28: @@
 [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.
+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 why this makes sense.
 ==See Also==
 {{USAJMO newbox|year=2022|before=First Question|num-a=2}}
 {{MAA Notice}}

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

Page

Toolbox

Search

Difference between revisions of "2022 USAJMO Problems/Problem 1"

Revision as of 20:46, 5 April 2024

Problem

Solution 1

See Also