2010 AMC 12B Problems/Problem 21
Contents
Problem 21
Let , and let
be a polynomial with integer coefficients such that
, and
.
What is the smallest possible value of ?
Solution 1
There must be some polynomial such that
Then, plugging in values of we get
Thus,
must be a multiple of
.
Now we show that there exists such that
We have
Thus,
for some
From here it is clear that
exists, since we can take
Therefore, our answer is
Solution 2
The evenly-spaced data suggests using discrete derivatives to tackle this problem. First, note that any polynomial of degree
![$P(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n$](http://latex.artofproblemsolving.com/d/0/c/d0c61a27ea483d0087f7676a6ce184af746f7989.png)
can also be written as
![$P(x) = b_0 + b_1 (x-1) + b_2 (x-1)(x-2) + \ldots + b_n (x-1)(x-1) \cdots (x-n)$](http://latex.artofproblemsolving.com/c/7/c/c7ceb63451cea3c05d040b809249609dc53bcf00.png)
Moreover, the coefficients are integers for
iff the coefficients
are integers for
. This latter form is convenient for calculating discrete derivatives of
.
The discrete derivative of a function is the related function
defined as
![$\Delta f(x) = f(x+1) - f(x)$](http://latex.artofproblemsolving.com/a/4/0/a40ea7880da0e4dceafa910def3c53a7564c293e.png)
With this definition, it's easy to see that for any positive integer we have
![$\Delta [(x-1)(x-2)\cdots(x-k)] = k(x-1)(x-2)\cdots(x-[k-1])$](http://latex.artofproblemsolving.com/f/2/2/f225d199590dedb5c4edd3f4e317da31068b9137.png)
This in turn allows us to use successive discrete derivatives evaluated at to calculate all of the coefficients
using
![$P(1)=b_0$](http://latex.artofproblemsolving.com/5/b/5/5b504d4a6cd17ef0f6456ccf351d4f87075b8757.png)
![$\Delta P(1) = b_1$](http://latex.artofproblemsolving.com/1/0/f/10f4bedc15ce7fa84437268db010893999897b07.png)
![$\Delta^2 P(1) = 2 b_2$](http://latex.artofproblemsolving.com/9/f/8/9f8c844ed80927e51332aec6290ae409267011fe.png)
![$\ldots$](http://latex.artofproblemsolving.com/3/9/5/3958e984d2597b35da7975f4503cdcf965a777f7.png)
![$\Delta^7 P(1) = 7! b_7$](http://latex.artofproblemsolving.com/0/b/5/0b50bab9c1cf3306d400ebf519085f550f2960d1.png)
We can also calculate the following table of discrete derivatives based on the data points given in the problem statement:
![]() | ||||||||
---|---|---|---|---|---|---|---|---|
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ||
![]() | ||||||||
![]() | ![]() |
Thus we can read down the column for to find that
for
. Interestingly, even if we choose
to have degree greater than
, the
coefficients of lowest order always satisfy these conditions. Moreover, it's straightforward to show that the
of degree
with
satisfying these conditions will fit the data given in the problem statement. Thus, to find minimal necessary and sufficient conditions on the value of
, we need only consider these
equations. As a result,
with integer coefficients fitting the given data exists iff
divides
for
. In other words, it's necessary and sufficient that
,
,
,
,
,
,
, and
.
The last condition holds iff divides evenly into
. Since such
will also satisfy the first
conditions, our answer is
.
See also
2010 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 20 |
Followed by Problem 22 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.