Difference between revisions of "1973 USAMO Problems/Problem 2"
(phew done) |
|||
(3 intermediate revisions by 2 users not shown) | |||
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= | + | <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 | + | <center> <math>X:1, 1, 3, 5, 11, 21, \dots</math>,</center> |
− | <center> <math>1 | + | <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. | ||
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 | + | |
+ | |||
+ | |||
+ | {{alternate solutions}} | ||
+ | |||
+ | ==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 18:54, 3 July 2013
Problem
Let and denote two sequences of integers defined as follows:
Thus, the first few terms of the sequences are:
Prove that, except for the "1", there is no term which occurs in both sequences.
Solution
We can look at each sequence :
- Proof that repeats :
The third and fourth terms are and . Plugging into the formula, we see that the next term is , and plugging and , we get that the next term is . Thus the sequence repeats, and the pattern is .
- Proof that repeats :
The first and second terms are and . Plugging into the formula, we see that the next term is , and plugging and , we get that the next term is . Thus the sequence repeats, and the pattern is .
Combining both results, we see that and are not congruent when and . 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.
See Also
1973 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.