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 "1997 USAMO Problems/Problem 3"

(→‎Solution)
(→‎Solution)
 
Line 5: Line 5:
 
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.  
 
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 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)$.
+
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 ==

Latest revision as of 20:15, 8 July 2021

Problem

Prove that for any integer $n$, there exists a unique polynomial $Q(x)$ with coefficients in $\{0,1,...,9\}$ such that $Q(-2)=Q(-5)=n$.

Solution

The problem implies that $Q(x) = (x+2)(x+5) \cdot H_y(x) + n$. We define $H_y(x) = a_0 + a_1x + ... + a_nx^n$. Then, after expanding, the coefficient of $x^k$ is $10a_k + 7a_{k-1} + a_{k-2}$ where $2 \le k \le n$. The constant term is $10a_0 + n$. Since this has to be within the set ${0,1,...,9}$, $a_0$ must be unique according to $n$. The linear term is determined by $10a_1 + 7a_0$, which also must be within the set ${0,1,...,9}$. Since $a_0$ is determined uniquely by $n$, in order to keep the linear coefficient in the set ${0,1,...,9}$, $a_1$ is also determined uniquely. With $a_0$ and $a_1$ determined uniquely, we move on to the general coefficient.

Note that $10a_k + 7a_{k-1} + a_{k-2}$ is in the set ${0,1,...,9}$. We define $J_h(x)$ to be a function determining the remainder when $x$ is divided by $10$. Thus, for all $x$, $0 \le J_h(x) \le 9$. Note also that $J_h(10a_k + 7a_{k-1} + a_{k-2}) = 10a_k + 7a_{k-1} + a_{k-2}$, since $10a_k + 7a_{k-1} + a_{k-2}$ is in the range of $J_h(x)$. Therefore, $J_h(7a_{k-1} + a_{k-2}) = 10a_k + 7a_{k-1} + a_{k-2}$, which results in $a_k = \lfloor \frac{7a_{k-1} + a_{k-2}}{10} \rfloor$ for all $2 \le k \le n$. Thus, $a_k$ is determined uniquely, since all coefficients $a_i$ where $0 \le i < k$ are uniquely determined, which in turn determines a unique polynomial $Q(x)$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1997_USAMO_Problems/Problem_3&oldid=157582"