Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 8"

m
m (typo correction)
 
Line 2: Line 2:
 
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.
 
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.
+
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 value of <math>{999 + 10 - 1 \choose 10} = {1008 \choose 10}</math>, so the answer is <math>008</math>.
 
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 value of <math>{999 + 10 - 1 \choose 10} = {1008 \choose 10}</math>, so the answer is <math>008</math>.
Line 8: Line 8:
  
 
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 <math>{{1008 \choose 10} \choose 1}</math>.  It so happens that these (with their corresponding expressions <math>{m \choose m - n}</math>) are the only four times this number appears in [[Pascal's Triangle]].
 
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 <math>{{1008 \choose 10} \choose 1}</math>.  It so happens that these (with their corresponding expressions <math>{m \choose m - n}</math>) are the only four times this number appears in [[Pascal's Triangle]].
−
 
  
 
==See also==
 
==See also==
−
 
+
{{Mock AIME box|year=2006-2007|n=4|num-b=7|num-a=9|source=125025}}
−
*[[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]]
 
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 15:20, 8 October 2007

Problem

The number of increasing sequences of positive integers $a_1 \le a_2 \le a_3 \le \cdots \le a_{10} \le 2007$ such that $a_i-i$ is even for $1\le i \le 10$ can be expressed as ${m \choose n}$ for some positive integers $m > n$. Compute the remainder when $m$ is divided by 1000.

Solution

The numbers $a_i - i$ are ten not-necessarily distinct even elements of the set $\{0, 1, 2, \ldots, 1997\}$. Moreover, given ten not-necessarily distinct elements of $\{0, 1, 2, \ldots, 1997\}$, we can reconstruct the list $a_1, a_2, \ldots, a_{10}$ 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 $\{0, 2, 4, \ldots, 1996\}$, which has 999 elements. This is a classic problem of combinatorics; in general, there are ${m + n - 1 \choose m}$ ways to choose $m$ things from a set of $n$ with replacement. In our case, this gives the value of ${999 + 10 - 1 \choose 10} = {1008 \choose 10}$, so the answer is $008$.


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 ${{1008 \choose 10} \choose 1}$. It so happens that these (with their corresponding expressions ${m \choose m - n}$) are the only four times this number appears in Pascal's Triangle.

See also

Mock AIME 4 2006-2007 (Problems, Source)
Preceded by
Problem 7 		Followed by
Problem 9
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_4_2006-2007_Problems/Problem_8&oldid=17615"