2017 AIME I Problems/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 .
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. However, this must be equal to . Therefore, the answer is .
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 .
Solution 3 (Major Bash)
Case 1: .
Subcase 1: Subcase 2: Subcase 3:
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
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 .
Let's visualize the problem as this: boys: (Let's call them Aiden, Brian, Clayton, Daniel, Eddie, Frankie) girls: (Let's call them Una, Vanessa, Wendy, Xawa, Yota, Zuzu) animals/pets: (Let's call them Woof, Meow, Bark, Wolf2, Meow2, Bark2) Now, we need to choose boys, girls, and animals to be qualified to go to the upcoming prom. Note that choosing animals out of the total animals to go to the prom is equivalent to choosing animals out of the total animals to NOT go to the prom. Thus, we can rewrite the sum as over all such that . (For instance, if and , we have ways, in which one of the possible ways is the set being . ) It is easy to see that the aforementioned sum is simply the number of ways to choose total entities from total entities, or , in which the last three digits are .
|2017 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|