Difference between revisions of "2016 UMO Problems/Problem 5"
(Created page with "==Problem == == Solution == == See Also == {{UMO box|year=2016|num-b=4|num-a=6}} [[Category:]]") |
|||
Line 1: | Line 1: | ||
==Problem == | ==Problem == | ||
+ | Let <math>a_0,a_1,a_2,\ldots</math> be a sequence of integers (positive, negative, or zero) such that for all nonnegative integers <math>n</math> and <math>k</math>, <math>a_{n+k}^2-(2k + 1)a_{n}a_{n+k} + (k^2 + k)a_n^2 = k^2-k</math>. Find all possible sequences <math>(a_n)</math>. | ||
− | == Solution == | + | == Solution 1 == |
+ | |||
+ | We can factor the equation as <math>[a_{n+k}-k\cdot a_n][a_{n+k}-(k + 1)\cdot a_n] = k(k-1)</math>. | ||
+ | Substituting in <math>k = 1</math>, we ﬁnd that either <math>a_{n+1} = 2a_n</math> or <math>a_{n+1} = a_n</math> for all integers <math>n</math>. If <math>p</math> is a prime such that <math>p \vert a_r</math>, then by repeatedly applying <math>a_{n+1} = 2a_n</math> or <math>a_{n+1} = a_n</math>, we ﬁnd that <math>p</math> divides <math>a_n</math> for all integers <math>n >= r</math>. Substituting <math>k = 2</math> and <math>n = r</math> into (1) we notice that the LHS is divisible by <math>p^2</math>, and the RHS is equal to <math>2</math>; hence <math>p^2 \vert 2</math>, which is a contradiction. Thus <math>a_n</math> is never divisible by any prime for any <math>n</math>, so <math>a_n = \pm 1</math>. In particular, <math>a_{n+1} = a_n</math> for all integers <math>n</math>, and <math>a_n</math> is constant either 1 or -1. Substituting either of these sequences into (1) shows that both are valid solutions. | ||
== See Also == | == See Also == | ||
{{UMO box|year=2016|num-b=4|num-a=6}} | {{UMO box|year=2016|num-b=4|num-a=6}} | ||
− | [[Category:]] | + | [[Category: Intermediate Number Theory Problems]] |
Latest revision as of 03:20, 22 January 2019
Problem
Let be a sequence of integers (positive, negative, or zero) such that for all nonnegative integers and , . Find all possible sequences .
Solution 1
We can factor the equation as . Substituting in , we ﬁnd that either or for all integers . If is a prime such that , then by repeatedly applying or , we ﬁnd that divides for all integers . Substituting and into (1) we notice that the LHS is divisible by , and the RHS is equal to ; hence , which is a contradiction. Thus is never divisible by any prime for any , so . In particular, for all integers , and is constant either 1 or -1. Substituting either of these sequences into (1) shows that both are valid solutions.
See Also
2016 UMO (Problems • Answer Key • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All UMO Problems and Solutions |