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"

(phew done)
 
m (→‎Problem)
Line 3: Line 3:
  
 
<center> <math>X_0=1</math>, <math>X_1=1</math>, <math>X_{n+1}=X_n+2X_{n-1}</math> <math>(n=1,2,3,\dots),</math></center>
 
<center> <math>X_0=1</math>, <math>X_1=1</math>, <math>X_{n+1}=X_n+2X_{n-1}</math> <math>(n=1,2,3,\dots),</math></center>
−
<center><math>Y_0=1</math>, <math>Y_1=1</math>, <math>Y_{n+1}=2Y_n+3Y_{n-1}</math> <math>(n=1,2,3,\dots)</math>.</center>
+
<center><math>Y_0=1</math>, <math>Y_1=7</math>, <math>Y_{n+1}=2Y_n+3Y_{n-1}</math> <math>(n=1,2,3,\dots)</math>.</center>
  
 
Thus, the first few terms of the sequences are:
 
Thus, the first few terms of the sequences are:
  
−
<center> <math>1</math>, <math>1</math>, <math>3</math>, <math>5</math>, <math>11</math>, <math>21</math>, <math>\dots</math>,</center>
+
<center> <math>X:1, 1, 3, 5, 11, 21, \dots</math>,</center>
−
<center> <math>1</math>, <math>7</math>, <math>17</math>, <math>55</math>, <math>161</math>, <math>487</math>, <math>\dots</math>.</center>
+
<center> <math>Y:1, 7, 17, 55, 161, 487, \dots</math>.</center>
  
 
Prove that, except for the "1", there is no term which occurs in both sequences.
 
Prove that, except for the "1", there is no term which occurs in both sequences.

Revision as of 15:18, 30 December 2008

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.

See also

1973 USAMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1973_USAMO_Problems/Problem_2&oldid=28993"