Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 8"
m |
|||
| Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
| − | The number of increasing | + | The number of [[increasing]] [[sequence]]s of [[positive integer]]s <math>a_1 \le a_2 \le a_3 \le \cdots \le a_{10} \le 2007</math> such that <math>a_i-i</math> is even for <math>1\le i \le 10</math> can be expressed as <math>{m \choose n}</math> for some positive integers <math>m > n</math>. Compute the [[remainder]] when <math>m</math> is divided by 1000. |
==Solution== | ==Solution== | ||
| + | The numbers <math>a_i - i</math> are ten not-necessarily distinct [[even]] [[element]]s of the [[set]] <math>\{0, 1, 2, \ldots, 1997\}</math>. Moreover, given ten not-necessarily distinct elements of <math>\{0, 1, 2, \ldots, 1997\}</math>, we can reconstruct the list <math>a_1, a_2, \ldots, a_10</math> in exactly one way, by adding 1 to the smallest, then adding 2 to the second-smallest (which might actually be equal to the smallest), and so on. | ||
| − | {{ | + | Thus, the answer is the same as the number of ways to choose 10 elements with replacement from the set <math>\{0, 2, 4, \ldots, 1996\}</math>, which has 999 elements. This is a classic problem of [[combinatorics]]; in general, there are <math>{m + n - 1 \choose m}</math> ways to choose <math>m</math> things from a set of <math>n</math> with replacement. In our case, this gives the answer of <math>{999 + 10 - 1 \choose 10} = {1008 \choose 10}</math>, so the answer is <math>008</math>. |
| + | Note that in fact, the answer is not unique because a many numbers can be represented as a [[binomial coefficient]] in more than one way. For instance, another such expression for the answer is <math>{{1008 \choose 10} \choose 1}</math>. It does happen in this case that the given expression is the first appearance of this number in [[Pascal's Triangle]]. | ||
| − | + | ||
| + | ==See also== | ||
*[[Mock AIME 4 2006-2007 Problems/Problem 9| Next Problem]] | *[[Mock AIME 4 2006-2007 Problems/Problem 9| Next Problem]] | ||
*[[Mock AIME 4 2006-2007 Problems/Problem 7| Previous Problem]] | *[[Mock AIME 4 2006-2007 Problems/Problem 7| Previous Problem]] | ||
*[[Mock AIME 4 2006-2007 Problems]] | *[[Mock AIME 4 2006-2007 Problems]] | ||
| + | |||
| + | [[Category:Intermediate Combinatorics Problems]] | ||
Revision as of 16:50, 10 February 2007
Problem
The number of increasing sequences of positive integers 
such that 
is even for 
can be expressed as 
for some positive integers 
. Compute the remainder when 
is divided by 1000.
Solution
The numbers 
are ten not-necessarily distinct even elements of the set 
. Moreover, given ten not-necessarily distinct elements of , we can reconstruct the list 
in exactly one way, by adding 1 to the smallest, then adding 2 to the second-smallest (which might actually be equal to the smallest), and so on.
Thus, the answer is the same as the number of ways to choose 10 elements with replacement from the set 
, which has 999 elements. This is a classic problem of combinatorics; in general, there are 
ways to choose things from a set of 
with replacement. In our case, this gives the answer of 
, so the answer is 
.
Note that in fact, the answer is not unique because a many numbers can be represented as a binomial coefficient in more than one way. For instance, another such expression for the answer is 
. It does happen in this case that the given expression is the first appearance of this number in Pascal's Triangle.
