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