Mock AIME 4 2006-2007 Problems/Problem 8
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 value 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 number of such sequences is . It does happen in this case that the given expression is the first appearance of this number in Pascal's Triangle.