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 "1973 USAMO Problems/Problem 2"

m (→‎Problem)
(→‎Solution 2)
 
(9 intermediate revisions by 3 users not shown)
Line 30: Line 30:
 
Combining both results, we see that <math>X_i</math> and <math>Y_j</math> are not congruent <math>\bmod{8}</math> when <math>i\geq 3</math> and <math>j\geq 2</math>. Thus after the "1", the terms of each sequence are not equal.
 
Combining both results, we see that <math>X_i</math> and <math>Y_j</math> are not congruent <math>\bmod{8}</math> when <math>i\geq 3</math> and <math>j\geq 2</math>. Thus after the "1", the terms of each sequence are not equal.
  
−
==See also==
+
 
 +
 
 +
 
 +
{{alternate solutions}}
 +
 
 +
==Solution 2==
 +
 
 +
We can solve this problem by finding a particular solution for each linear recurrence.
 +
 
 +
<math>X_{n+1} - X_n - 2X_{n-1} = 0</math> with characteristic polynomial
 +
 
 +
<math>X^2 - X - 2 = (X - 2)(X + 1)</math>, so <math>X = -1, 2</math>
 +
 
 +
<math>X_n = A(2)^n + B(-1)^n</math>
 +
 
 +
After plugging in to find the particular solution:
 +
 
 +
<math>X_0 = 1 = A + B</math>
 +
 
 +
<math>X_1 = 1 = 2A - B</math>
 +
 
 +
<math>A = \frac{1}{3}</math> and <math>B = \frac{2}{3}</math>, so
 +
 
 +
<math>X_n = \frac{1}{3}(2)^n + \frac{2}{3}(-1)^n</math>
 +
 
 +
Doing the same for <math>Y_n</math>, we get
 +
 
 +
<math>Y_n = 2(3)^n - (-1)^n</math>
 +
 
 +
We know they're equal at <math>n = 0</math>, so let's set them equal and compare.
 +
 
 +
<math>2(3)^n - (-1)^n = \frac{1}{3}((2)^n + 2(-1)^n)</math>
 +
 
 +
<math>6(3)^n - 3(-1)^n = (2)^n + 2(-1)^n</math>
 +
 
 +
<math>6(3)^n - 2^n = 5(-1)^n</math>
 +
 
 +
By induction, we know in general that <math>(\alpha + 1)^n > \alpha^n</math> for all <math>\alpha, n > 0</math>, so <math>6(3)^n > 2^n</math> for all <math>n > 1</math>.
 +
 
 +
Therefore, the left hand side is always increasing and will never equal 5 again, so equality between <math>X_n</math> and <math>Y_n</math> only holds when <math>n = 0</math>, so they only share 1 term.
 +
 
 +
==See Also==
  
 
{{USAMO box|year=1973|num-b=1|num-a=3}}
 
{{USAMO box|year=1973|num-b=1|num-a=3}}
 +
{{MAA Notice}}
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 11:38, 3 June 2024

Problem

Let $\{X_n\}$ and $\{Y_n\}$ denote two sequences of integers defined as follows:

$X_0=1$, $X_1=1$, $X_{n+1}=X_n+2X_{n-1}$ $(n=1,2,3,\dots),$
$Y_0=1$, $Y_1=7$, $Y_{n+1}=2Y_n+3Y_{n-1}$ $(n=1,2,3,\dots)$.

Thus, the first few terms of the sequences are:

$X:1, 1, 3, 5, 11, 21, \dots$,
$Y:1, 7, 17, 55, 161, 487, \dots$.

Prove that, except for the "1", there is no term which occurs in both sequences.

Solution

We can look at each sequence $\bmod{8}$:

$X$: $1$, $1$, $3$, $5$, $3$, $5$, $\dots$,
$Y$: $1$, $7$, $1$, $7$, $1$, $7$, $\dots$.
  • Proof that $X$ repeats $\bmod{8}$:

The third and fourth terms are $3$ and $5$ $\bmod{8}$. Plugging into the formula, we see that the next term is $11\equiv 3\bmod{8}$, and plugging $5$ and $3$, we get that the next term is $13\equiv 5\bmod{8}$. Thus the sequence $X$ repeats, and the pattern is $3,5,3,5,\dots$.

  • Proof that $Y$ repeats $\bmod{8}$:

The first and second terms are $1$ and $7$ $\bmod{8}$. Plugging into the formula, we see that the next term is $17\equiv 1\bmod{8}$, and plugging $7$ and $1$, we get that the next term is $23\equiv 7\bmod{8}$. Thus the sequence $Y$ repeats, and the pattern is $1,7,1,7,\dots$.


Combining both results, we see that $X_i$ and $Y_j$ are not congruent $\bmod{8}$ when $i\geq 3$ and $j\geq 2$. Thus after the "1", the terms of each sequence are not equal.



Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Solution 2

We can solve this problem by finding a particular solution for each linear recurrence.

$X_{n+1} - X_n - 2X_{n-1} = 0$ with characteristic polynomial

$X^2 - X - 2 = (X - 2)(X + 1)$, so $X = -1, 2$

$X_n = A(2)^n + B(-1)^n$

After plugging in to find the particular solution:

$X_0 = 1 = A + B$

$X_1 = 1 = 2A - B$

$A = \frac{1}{3}$ and $B = \frac{2}{3}$, so

$X_n = \frac{1}{3}(2)^n + \frac{2}{3}(-1)^n$

Doing the same for $Y_n$, we get

$Y_n = 2(3)^n - (-1)^n$

We know they're equal at $n = 0$, so let's set them equal and compare.

$2(3)^n - (-1)^n = \frac{1}{3}((2)^n + 2(-1)^n)$

$6(3)^n - 3(-1)^n = (2)^n + 2(-1)^n$

$6(3)^n - 2^n = 5(-1)^n$

By induction, we know in general that $(\alpha + 1)^n > \alpha^n$ for all $\alpha, n > 0$, so $6(3)^n > 2^n$ for all $n > 1$.

Therefore, the left hand side is always increasing and will never equal 5 again, so equality between $X_n$ and $Y_n$ only holds when $n = 0$, so they only share 1 term.

See Also

1973 USAMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5
All USAMO 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=1973_USAMO_Problems/Problem_2&oldid=220014"