2020 AIME II Problems/Problem 14
Contents
Problem
For real number let be the greatest integer less than or equal to , and define to be the fractional part of . For example, and . Define , and let be the number of real-valued solutions to the equation for . Find the remainder when is divided by .
Solution 1
\[ \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1 .\] A combinatorical argument exists which is the official solution, but I will present another here for the sake of variety.
Applying algebraic manipulation and the hockey-stick identity times gives \begin{align*} \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1 =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} \binom{z-y}{0}\\ =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \binom{2020-y}{1}\\ =\sum_{x=17}^{2019} \binom{2021-x}{2}\\ =\binom{2005}{3} \end{align*}
Solution 2
To solve , we need to solve where , and to solve that we need to solve where .
It is clear to see for some integer there is exactly one value of in the interval where To understand this, imagine the graph of on the interval The graph starts at , is continuous and increasing, and approaches . So as long as , there will be a solution for in the interval.
Using this logic, we can find the number of solutions to . For every interval where there will be one solution for x in that interval. However, the question states , but because doesn't work we can change it to . Therefore, , and there are solutions to .
We can solve similarly. to satisfy the bounds of , so there are solutions to , and to satisfy the bounds of .
Going back to , there is a single solution for z in the interval , where . (We now have an upper bound for because we know .) There are solutions for , and the floors of these solutions create the sequence
Lets first look at the solution of where . Then would have solutions, and the floors of these solutions would also create the sequence .
If we used the solution of where , there would be solutions for . If we used the solution of where , there would be solutions for , and so on. So for the solution of where , there will be solutions for
If we now look at the solution of where , there would be solutions for . If we looked at the solution of where , there would be solutions for , and so on.
The total number of solutions to is . Using the hockey stick theorem, we see this equals , and when we take the remainder of that number when divided by , we get the answer,
~aragornmf
Solution 2 (Official MAA)
For any nonnegative integer , the function increases on the interval , with and for every in this interval. On this interval , which takes on every real value in the interval exactly once. Thus for each nonnegative real number , the equation has exactly one solution for every .
For each integer there is exactly one with such that ; likewise for each integer there is exactly one with and such that . Finally, for each integer there is exactly one with , , and such that .
Thus has exactly one solution with for each triple of integers with , noting that is not a solution. This nondecreasing ordered triple can be identified with a multiset of three elements of the set of integers , which can be selected in ways. Thus
Video Solution
https://youtu.be/bz5N-jI2e0U?t=515
See Also
2020 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
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.