2017 AIME I Problems/Problem 7
Contents
[hide]- 1 Problem 7
- 2 Major Note
- 3 Solution 34987029836757926304875 (Committee Forming)
- 4 Solution 1 but different (Committee Forming)
- 5 Solution 2 (Committee Forming but slightly more bashy)
- 6 Solution 3 (Major Major Bash)
- 7 Solution 4
- 8 Solution 5 (Committee Forming but different)
- 9 Solution 5 but different (Committee Forming)
- 10 Solution 6(NICE Journal)
- 11 Remark
- 12 See Also
Problem 7
For nonnegative integers and with , let . Let denote the sum of all , where and are nonnegative integers with . Find the remainder when is divided by .
Major Note
Most solutions use committee forming (except for the bash solution). To understand more about the techniques used, visit the committee forming page for more information.
Solution 34987029836757926304875 (Committee Forming)
Let , and note that . The problem thus asks for the sum over all such that . Consider an array of 18 dots, with 3 columns of 6 dots each. The desired expression counts the total number of ways to select 6 dots by considering each column separately, which is equal to . Therefore, the answer is .
-rocketscience
Solution 1 but different (Committee Forming)
Alternatively, one can note that we can consider groups where is constant, say . Fix any value of . Then the sum of all of the values of such that is which by Vandermonde's is . Remember, that expression is the resulting sum for a fixed . So, for , we want . This is (by Vandermonde's or committee forming) ~ firebolt360
Note
Now just a quick explanation for people who don't fully understand Vandermonde's. Take the first part, . Consider different groups, and both of size people. We wish to chose peoples from and people from . In total, we chose people. We can then draw a bijection towards choosing people from , which has size . So, it is . Similarly, for , we see that . Now the total is , and the sum is . So, we get . See committee forming for more information ~ firebolt360
Solution 2 (Committee Forming but slightly more bashy)
Treating as , this problem asks for But can be computed through the following combinatorial argument. Choosing elements from a set of size is the same as splitting the set into two sets of size and choosing elements from one, from the other where . The number of ways to perform such a procedure is simply . Therefore, the requested sum is As such, our answer is .
- Awsomness2000
Solution 3 (Major Major Bash)
Case 1: .
Subcase 1: Subcase 2: Subcase 3:
Case 2:
By just switching and in all of the above cases, we will get all of the cases such that is true. Therefore, this case is also
Case 3:
Solution 4
We begin as in solution 1 to rewrite the sum as over all such that . Consider the polynomial . We can see the sum we wish to compute is just the coefficient of the term. However . Therefore, the coefficient of the term is just so the answer is .
- mathymath
Solution 5 (Committee Forming but different)
Let . Then , and . The problem thus asks for Suppose we have red balls, green balls, and blue balls lined up in a row, and we want to choose balls from this set of balls by considering each color separately. Over all possible selections of balls from this set, there are always a nonnegative number of balls in each color group. The answer is .
Solution 5 but different (Committee Forming)
Since , we can rewrite as . Consider the number of ways to choose a committee of 6 people from a group of 6 democrats, 6 republicans, and 6 independents. We can first pick democrats, then pick republicans, provided that . Then we can pick the remaining people from the independents. But this is just , so the sum of all is equal to the number of ways to choose this committee. On the other hand, we can simply pick any 6 people from the total politicians in the group. Clearly, there are ways to do this. So the desired quantity is equal to . We can then compute (routinely) the last 3 digits of as .
Solution 6(NICE Journal)
Note that . So we have . If we think about this this is essentially choosing a group of people from people, a group of people from people, and a group of from another group of people. This is nothing but choosing people from a group of people. This is nothing but . ~coolmath_2018
Remark
This problem is an example of the generalization of Vandermonde's theorem, which states that for nonnegative and , we have ~eibc
See Also
2017 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.