2010 AMC 12B Problems/Problem 21
Let , and let be a polynomial with integer coefficients such that
What is the smallest possible value of ?
There must be some polynomial such that
Then, plugging in values of we get
Thus, the least value of must be the . Solving, we receive , so our answer is .
(This solution appears to be incomplete in that it only shows that being a multiple of is a necessary condition for to have integer coefficients. However, it's not clear at this point that is sufficient to guarantee that has only integer coefficients. For example, at this point how do we know that for the equations above for , , , and don't require that, say, the second coefficient of is ?)
The evenly-spaced data suggests using discrete derivatives to tackle this problem. First, note that any polynomial of degree
can also be written as
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
With this definition, it's easy to see that for any positive integer we have
This in turn allows us to use successive discrete derivatives evaluated at to calculate all of the coefficients using
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
The last condition holds iff divides evenly into . Since such will also satisfy the first conditions, our answer is .
|2010 AMC 12B (Problems • Answer Key • Resources)|
|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|