Difference between revisions of "2018 AIME I Problems/Problem 1"
m (Removed protection from "2018 AIME I Problems/Problem 1") |
|||
Line 1: | Line 1: | ||
+ | ==Question== | ||
+ | Let <math>S</math> be the number of ordered pairs of integers <math>(a,b)</math> with <math>1 \leq a \leq 100</math> and <math>b \geq 0</math> such that the polynomial <math>x^2+ax+b</math> can be factored into the product of two (not necessarily distinct) linear factors with integer coefficients. Find the remainder when <math>S</math> is divided by <math>1000</math>. | ||
+ | ==Solution== | ||
+ | You let the linear factors be as <math>(x+c)(x+d)</math>. | ||
+ | Then, obviously <math>a=c+d</math> and <math>b=cd</math>. | ||
+ | We know that <math>1\le a\le 100</math> and <math>b\ge 0</math>, so <math>c</math> and <math>d</math> both have to be positive. | ||
+ | However, <math>a</math> cannot be <math>0</math>, so at least one of <math>c</math> and <math>d</math> must be greater than <math>0</math>, ie positive. | ||
+ | Also, <math>a</math> cannot be greater than <math>100</math>, so <math>c+d</math> must be less than or equal to <math>100</math>. | ||
+ | Essentially, if we plot the solutions, we get a triangle on the coordinate plane with vertices <math>(0,0), (0, 100),</math> and <math>(100,0)</math>. Remember that <math>(0,0)</math> does not work, so there is a square with top right corner <math>(1,1)</math>. | ||
+ | Note that <math>c</math> and <math>d</math> are interchangeable, since they end up as <math>a</math> and <math>b</math> in the end anyways. Thus, we simply draw a line from <math>(1,1)</math> to <math>(50,50)</math>, designating one of the halves as our solution (since the other side is simply the coordinates flipped). | ||
+ | We note that the pattern from <math>(1,1)</math> to <math>(50,50)</math> is <math>2+3+4+\dots+51</math> solutions and from <math>(51, 49)</math> to <math>(100,0)</math> is <math>50+49+48+\dots+1</math> solutions, since we can decrease the <math>y</math>-value by <math>1</math> until <math>0</math> for each coordinate. | ||
+ | Adding up gives <cmath>\dfrac{2+51}{2}\cdot 50+\dfrac{50+1}{2}\cdot 50.</cmath> | ||
+ | This gives us <math>2600</math>, and <math>2600\equiv 600 \bmod{1000}.</math> | ||
− | + | Thus, the answer is: <cmath>\boxed{600}.</cmath> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Revision as of 16:08, 7 March 2018
Question
Let be the number of ordered pairs of integers
with
and
such that the polynomial
can be factored into the product of two (not necessarily distinct) linear factors with integer coefficients. Find the remainder when
is divided by
.
Solution
You let the linear factors be as .
Then, obviously and
.
We know that and
, so
and
both have to be positive.
However, cannot be
, so at least one of
and
must be greater than
, ie positive.
Also, cannot be greater than
, so
must be less than or equal to
.
Essentially, if we plot the solutions, we get a triangle on the coordinate plane with vertices and
. Remember that
does not work, so there is a square with top right corner
.
Note that and
are interchangeable, since they end up as
and
in the end anyways. Thus, we simply draw a line from
to
, designating one of the halves as our solution (since the other side is simply the coordinates flipped).
We note that the pattern from to
is
solutions and from
to
is
solutions, since we can decrease the
-value by
until
for each coordinate.
Adding up gives
This gives us
, and
Thus, the answer is: