Difference between revisions of "1997 USAMO Problems/Problem 3"
m (added solution tag, USAMO box, and category.) |
(→Solution) |
||
(6 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Prove that for any integer <math>n</math>, there exists a unique polynomial <math>Q</math> with coefficients in <math>\{0,1,...,9\}</math> such that <math>Q(-2)=Q(-5)=n</math>. | + | Prove that for any integer <math>n</math>, there exists a unique polynomial <math>Q(x)</math> with coefficients in <math>\{0,1,...,9\}</math> such that <math>Q(-2)=Q(-5)=n</math>. |
== Solution == | == Solution == | ||
− | {{ | + | The problem implies that <math>Q(x) = (x+2)(x+5) \cdot H_y(x) + n</math>. We define <math>H_y(x) = a_0 + a_1x + ... + a_nx^n</math>. Then, after expanding, the coefficient of <math>x^k</math> is <math>10a_k + 7a_{k-1} + a_{k-2}</math> where <math>2 \le k \le n</math>. The constant term is <math>10a_0 + n</math>. Since this has to be within the set <math>{0,1,...,9}</math>, <math>a_0</math> must be unique according to <math>n</math>. The linear term is determined by <math>10a_1 + 7a_0</math>, which also must be within the set <math>{0,1,...,9}</math>. Since <math>a_0</math> is determined uniquely by <math>n</math>, in order to keep the linear coefficient in the set <math>{0,1,...,9}</math>, <math>a_1</math> is also determined uniquely. With <math>a_0</math> and <math>a_1</math> determined uniquely, we move on to the general coefficient. |
+ | |||
+ | Note that <math>10a_k + 7a_{k-1} + a_{k-2}</math> is in the set <math>{0,1,...,9}</math>. We define <math>J_h(x)</math> to be a function determining the remainder when <math>x</math> is divided by <math>10</math>. Thus, for all <math>x</math>, <math>0 \le J_h(x) \le 9</math>. Note also that <math>J_h(10a_k + 7a_{k-1} + a_{k-2}) = 10a_k + 7a_{k-1} + a_{k-2}</math>, since <math>10a_k + 7a_{k-1} + a_{k-2}</math> is in the range of <math>J_h(x)</math>. Therefore, <math>J_h(7a_{k-1} + a_{k-2}) = 10a_k + 7a_{k-1} + a_{k-2}</math>, which results in <math>a_k = \lfloor \frac{7a_{k-1} + a_{k-2}}{10} \rfloor</math> for all <math>2 \le k \le n</math>. Thus, <math>a_k</math> is determined uniquely, since all coefficients <math>a_i</math> where <math>0 \le i < k</math> are uniquely determined, which in turn determines a unique polynomial <math>Q(x)</math>. | ||
+ | |||
== See Also == | == See Also == | ||
− | {{USAMO | + | {{USAMO newbox|year=1997|num-b=2|num-a=4}} |
[[Category:Olympiad Algebra Problems]] | [[Category:Olympiad Algebra Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 20:15, 8 July 2021
Problem
Prove that for any integer , there exists a unique polynomial with coefficients in such that .
Solution
The problem implies that . We define . Then, after expanding, the coefficient of is where . The constant term is . Since this has to be within the set , must be unique according to . The linear term is determined by , which also must be within the set . Since is determined uniquely by , in order to keep the linear coefficient in the set , is also determined uniquely. With and determined uniquely, we move on to the general coefficient.
Note that is in the set . We define to be a function determining the remainder when is divided by . Thus, for all , . Note also that , since is in the range of . Therefore, , which results in for all . Thus, is determined uniquely, since all coefficients where are uniquely determined, which in turn determines a unique polynomial .
See Also
1997 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.