1997 USAMO Problems/Problem 3

Revision as of 20:15, 8 July 2021 by Eca123 (talk | contribs) (Solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 (ProblemsResources)
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

Invalid username
Login to AoPS