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 < | + | 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 21: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.