Difference between revisions of "1973 USAMO Problems/Problem 2"
m (→Solution) |
|||
Line 38: | Line 38: | ||
{{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]] |
Revision as of 18:54, 3 July 2013
Problem
Let and
denote two sequences of integers defined as follows:
![$X_0=1$](http://latex.artofproblemsolving.com/c/e/b/cebce4cef53ec8891f6b19b9e15609f8f67e3ce4.png)
![$X_1=1$](http://latex.artofproblemsolving.com/4/c/9/4c98f37726f1b237003a06d40752524a28e99f47.png)
![$X_{n+1}=X_n+2X_{n-1}$](http://latex.artofproblemsolving.com/7/9/f/79f9ae578208dd5fd22233a74eb9958b7fa123db.png)
![$(n=1,2,3,\dots),$](http://latex.artofproblemsolving.com/a/2/7/a27887235fc6fe223896299960f50abedf4113f4.png)
![$Y_0=1$](http://latex.artofproblemsolving.com/7/9/7/79793a5127f0c02da1cd1496fc8a96c10a26232a.png)
![$Y_1=7$](http://latex.artofproblemsolving.com/e/0/e/e0e33be65971d1a5f4e92726ac4f5928d8c6ab59.png)
![$Y_{n+1}=2Y_n+3Y_{n-1}$](http://latex.artofproblemsolving.com/0/e/7/0e713f61302bc1d06796c423e76fcc2e456b6df5.png)
![$(n=1,2,3,\dots)$](http://latex.artofproblemsolving.com/0/3/8/0382bde36fe67f5296e632643ceb5d774545d3b6.png)
Thus, the first few terms of the sequences are:
![$X:1, 1, 3, 5, 11, 21, \dots$](http://latex.artofproblemsolving.com/4/2/3/423b49eb7fcf22e80c66be8b01f2cbdd2d9c34fe.png)
![$Y:1, 7, 17, 55, 161, 487, \dots$](http://latex.artofproblemsolving.com/8/9/3/89343c5c6c83f02fb1b692cc7d7d845c7d56e3fe.png)
Prove that, except for the "1", there is no term which occurs in both sequences.
Solution
We can look at each sequence :
![$X$](http://latex.artofproblemsolving.com/6/a/4/6a47ca0fe7cb276abc022af6ac88ddae1a9d6894.png)
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$3$](http://latex.artofproblemsolving.com/7/c/d/7cde695f2e4542fd01f860a89189f47a27143b66.png)
![$5$](http://latex.artofproblemsolving.com/7/9/0/79069377f91364c2f87a64e5f9f562a091c8a6c1.png)
![$3$](http://latex.artofproblemsolving.com/7/c/d/7cde695f2e4542fd01f860a89189f47a27143b66.png)
![$5$](http://latex.artofproblemsolving.com/7/9/0/79069377f91364c2f87a64e5f9f562a091c8a6c1.png)
![$\dots$](http://latex.artofproblemsolving.com/6/4/6/64683f315744c851898c8d65dace1a8aa31b93ab.png)
![$Y$](http://latex.artofproblemsolving.com/c/e/5/ce58e4af225c93d08606c26554caaa5ae32edeba.png)
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$7$](http://latex.artofproblemsolving.com/e/0/a/e0a0db32027a732ac57d37ef2ae9bb150f65b108.png)
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$7$](http://latex.artofproblemsolving.com/e/0/a/e0a0db32027a732ac57d37ef2ae9bb150f65b108.png)
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$7$](http://latex.artofproblemsolving.com/e/0/a/e0a0db32027a732ac57d37ef2ae9bb150f65b108.png)
![$\dots$](http://latex.artofproblemsolving.com/6/4/6/64683f315744c851898c8d65dace1a8aa31b93ab.png)
- 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.