2017 AIME I Problems/Problem 7
Contents
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
.
Solution 1
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
.
-rocketscience
Solution 2
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 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
Let's visualize the problem as this:
boys: (Let's call them Eddie, Edmund, Luke, Kareem, Sharjeel, and Bob)
girls: (Let's call them Zuzu, Edmund's imaginary girlfriend, Luke's imaginary girlfriend, Kareem's imaginary girlfriend, Sharjeel's imaginary girlfriend, and Billie (transgender girl))
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
.
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.