1997 USAMO Problems/Problem 3

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)$ .

1997 USAMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

1997 USAMO Problems/Problem 3

Problem

Solution

See Also