Difference between revisions of "2010 AMC 12B Problems/Problem 21"
m (→Solution 2) |
|||
(18 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
− | == Problem | + | == Problem == |
Let <math>a > 0</math>, and let <math>P(x)</math> be a polynomial with integer coefficients such that | Let <math>a > 0</math>, and let <math>P(x)</math> be a polynomial with integer coefficients such that | ||
<center> | <center> | ||
− | <math>P(1) = P(3) = P(5) = P(7) = a</math>, and<br | + | <math>P(1) = P(3) = P(5) = P(7) = a</math>, |
+ | and <br > | ||
<math>P(2) = P(4) = P(6) = P(8) = -a</math>. | <math>P(2) = P(4) = P(6) = P(8) = -a</math>. | ||
</center> | </center> | ||
Line 12: | Line 13: | ||
== Solution == | == Solution == | ||
− | + | We observe that because <math>P(1) = P(3) = P(5) = P(7) = a</math>, if we define a new polynomial <math>R(x)</math> such that <math>R(x) = P(x) - a</math>, <math>R(x)</math> has roots when <math>P(x) = a</math>; namely, when <math>x=1,3,5,7</math>. | |
+ | |||
+ | Thus since <math>R(x)</math> has roots when <math>x=1,3,5,7</math>, we can factor the product <math>(x-1)(x-3)(x-5)(x-7)</math> out of <math>R(x)</math> to obtain a new polynomial <math>Q(x)</math> such that <math>(x-1)(x-3)(x-5)(x-7)(Q(x)) = R(x) = P(x) - a</math>. | ||
Then, plugging in values of <math>2,4,6,8,</math> we get | Then, plugging in values of <math>2,4,6,8,</math> we get | ||
− | < | + | <cmath>P(2)-a=(2-1)(2-3)(2-5)(2-7)Q(2) = -15Q(2) = -2a</cmath> |
+ | <cmath>P(4)-a=(4-1)(4-3)(4-5)(4-7)Q(4) = 9Q(4) = -2a</cmath> | ||
+ | <cmath>P(6)-a=(6-1)(6-3)(6-5)(6-7)Q(6) = -15Q(6) = -2a</cmath> | ||
+ | <cmath>P(8)-a=(8-1)(8-3)(8-5)(8-7)Q(8) = 105Q(8) = -2a</cmath> | ||
− | <math> | + | <math>-2a=-15Q(2)=9Q(4)=-15Q(6)=105Q(8).</math> |
+ | Thus, the least value of <math>a</math> must be the <math>\text{lcm}(15,9,15,105)</math>. | ||
+ | Solving, we receive <math>315</math>, so our answer is <math> \boxed{\textbf{(B)}\ 315} </math>. | ||
− | <math> | + | To complete the solution, we can let <math>a = 315</math>, and then try to find <math>Q(x)</math>. We know from the above calculation that <math>Q(2)=42, Q(4)=-70, Q(6)=42</math>, and <math>Q(8)=-6</math>. Then we can let <math>Q(x) = T(x)(x-2)(x-6)+42</math>, getting <math>T(4)=28, T(8)=-4</math>. Let <math>T(x)=L(x)(x-8)-4</math>, then <math>L(4)=-8</math>. Therefore, it is possible to choose <math>T(x) = -8(x-8)-4 = -8x + 60</math>, so the goal is accomplished. As a reference, the polynomial we get is |
− | < | + | <cmath>P(x) = (x-1)(x-3)(x-5)(x-7)((-8x + 60)(x-2)(x-6)+42) + 315</cmath> |
+ | <cmath> = -8 x^7+252 x^6-3248 x^5+22050 x^4-84392 x^3+179928 x^2-194592 x+80325 </cmath> | ||
− | <math>- | + | == Solution 2 == |
− | Thus, the | + | |
− | + | The evenly-spaced data suggests using [[discrete derivative|discrete derivatives]] to tackle this problem. First, note that any polynomial of degree <math>n</math> | |
+ | |||
+ | <center><math>P(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n</math></center> | ||
+ | |||
+ | can also be written as | ||
+ | |||
+ | <center><math>P(x) = b_0 + b_1 (x-1) + b_2 (x-1)(x-2) + \ldots + b_n (x-1)(x-1) \cdots (x-n)</math>.</center> | ||
+ | |||
+ | Moreover, the coefficients <math>a_i</math> are integers for <math>i=1, 2, \ldots n</math> iff the coefficients <math>b_i</math> are integers for <math>i=1, 2, \ldots n</math>. This latter form is convenient for calculating discrete derivatives of <math>P(x)</math>. | ||
+ | |||
+ | The discrete derivative of a function <math>f(x)</math> is the related function <math>\Delta f(x)</math> defined as | ||
+ | |||
+ | <center><math>\Delta f(x) = f(x+1) - f(x)</math>.</center> | ||
+ | |||
+ | With this definition, it's easy to see that for any positive integer <math>k</math> we have | ||
+ | |||
+ | <center><math>\Delta [(x-1)(x-2)\cdots(x-k)] = k(x-1)(x-2)\cdots(x-[k-1])</math>.</center> | ||
+ | |||
+ | This in turn allows us to use successive discrete derivatives evaluated at <math>x=1</math> to calculate all of the coefficients <math>b_i</math> using | ||
+ | |||
+ | <center><math>P(1)=b_0</math>, <math>\Delta P(1) = b_1</math>, <math>\Delta^2 P(1) = 2 b_2</math>, <math>\ldots</math>, <math>\Delta^7 P(1) = 7! b_7</math>.</center> | ||
+ | |||
+ | We can also calculate the following table of discrete derivatives based on the data points given in the problem statement: | ||
+ | |||
+ | <center> | ||
+ | |||
+ | <table frame='box' rules='all' cellpadding='3'> | ||
+ | |||
+ | <tr><th /><th colspan='8'><math>x</math></th></tr> | ||
+ | |||
+ | <tr><td align='right'></td><td align='center'><math>1</math></td><td align='center'><math>2</math></td><td align='center'><math>3</math></td><td align='center'><math>4</math></td><td align='center'><math>5</math></td><td align='center'><math>6</math></td><td align='center'><math>7</math></td><td align='center'><math>8</math></td></tr> | ||
+ | |||
+ | <tr><td align='right'><math>P(x)</math></td><td align='right'><math>a</math></td><td align='right'><math>-a</math></td><td align='right'><math>a</math></td><td align='right'><math>-a</math></td><td align='right'><math>a</math></td><td align='right'><math>-a</math></td><td align='right'><math>a</math></td><td align='right'><math>-a</math></td></tr> | ||
+ | |||
+ | <tr><td align='right'><math>\Delta P(x)</math></td><td align='right'><math>-2a</math></td><td align='right'><math>2a</math></td><td align='right'><math>-2a</math></td><td align='right'><math>2a</math></td><td align='right'><math>-2a</math></td><td align='right'><math>2a</math></td><td align='right'><math>-2a</math></td><td /></tr> | ||
+ | |||
+ | <tr><td align='right'><math>\Delta^2 P(x)</math></td><td align='right'><math>4a</math></td><td align='right'><math>-4a</math></td><td align='right'><math>4a</math></td><td align='right'><math>-4a</math></td><td align='right'><math>4a</math></td><td align='right'><math>-4a</math></td><td /><td /></tr> | ||
+ | |||
+ | <tr><td colspan='9' align='center'><math>\vdots</math></td></tr> | ||
+ | |||
+ | <tr><td align='right'><math>\Delta^7 P(x)</math></td><td align='right'><math>-2^7 a</math></td><td /><td /><td /><td /><td /><td /><td /></tr> | ||
+ | |||
+ | </table> | ||
+ | |||
+ | </center> | ||
+ | |||
+ | Thus we can read down the column for <math>x=1</math> to find that <math>k! b_k = (-2)^k a</math> for <math>k = 0, 1, \ldots, 7</math>. Interestingly, even if we choose <math>P(x)</math> to have degree greater than <math>7</math>, the <math>8</math> coefficients of lowest order always satisfy these conditions. Moreover, it's straightforward to show that the <math>P(x)</math> of degree <math>7</math> with <math>b_k</math> satisfying these conditions will fit the data given in the problem statement. Thus, to find minimal necessary and sufficient conditions on the value of <math>a</math>, we need only consider these <math>8</math> equations. As a result, <math>P(x)</math> with integer coefficients fitting the given data exists iff <math>k!</math> divides <math>2^k a</math> for <math>k = 0, 1, \ldots, 7</math>. In other words, it's necessary and sufficient that | ||
+ | |||
+ | <center> | ||
+ | |||
+ | <math>0! | a</math>, | ||
+ | |||
+ | <math>1! | 2a</math>, | ||
+ | |||
+ | <math>2! | 2^2 a</math>, | ||
+ | |||
+ | <math>3! | 2^3 a</math>, | ||
+ | |||
+ | <math>4! | 2^4 a</math>, | ||
+ | |||
+ | <math>5! | 2^5 a</math>, | ||
+ | |||
+ | <math>6! | 2^6 a</math>, and | ||
+ | |||
+ | <math>7! | 2^7 a</math>. | ||
+ | |||
+ | </center> | ||
+ | |||
+ | The last condition holds if <math>7 \cdot 3 \cdot 5 \cdot 3 = 315</math> divides evenly into <math>a</math>. Since such <math>a</math> will also satisfy the first <math>7</math> conditions, our answer is <math> \boxed{\textbf{(B)}\ 315} </math>. | ||
== See also == | == See also == | ||
− | {{AMC12 box|year=2010|num-b=20|num-a=22|ab=B}} | + | {{AMC12 box|year=2010|ab=B|num-b=20|num-a=22}} |
+ | {{AMC10 box|ab=B|year=2010|after=Last Problem|num-b=24}} | ||
+ | [[Category:Intermediate Algebra Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 00:04, 26 February 2024
Contents
Problem
Let , and let
be a polynomial with integer coefficients such that
,
and
.
What is the smallest possible value of ?
Solution
We observe that because , if we define a new polynomial
such that
,
has roots when
; namely, when
.
Thus since has roots when
, we can factor the product
out of
to obtain a new 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
.
To complete the solution, we can let , and then try to find
. We know from the above calculation that
, and
. Then we can let
, getting
. Let
, then
. Therefore, it is possible to choose
, so the goal is accomplished. As a reference, the polynomial we get 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 if 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 |
2010 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Problem | |
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 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.