Difference between revisions of "2020 AIME II Problems/Problem 14"
(→Solution) |
|||
(17 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | For real number <math>x</math> let <math>\lfloor x\rfloor</math> be the greatest integer less than or equal to <math>x</math>, and define <math>\{x\} = x - \lfloor x \rfloor</math> to be the fractional part of <math>x</math>. For example, <math>\{3\} = 0</math> and <math>\{4.56\} = 0.56</math>. Define <math>f(x)=x\{x\}</math>, and let <math>N</math> be the number of real-valued solutions to the equation <math>f(f(f(x)))=17</math> for <math>0\leq x\leq 2020</math>. Find the remainder when <math>N</math> is divided by <math>1000</math>. | + | For a real number <math>x</math> let <math>\lfloor x\rfloor</math> be the greatest integer less than or equal to <math>x</math>, and define <math>\{x\} = x - \lfloor x \rfloor</math> to be the fractional part of <math>x</math>. For example, <math>\{3\} = 0</math> and <math>\{4.56\} = 0.56</math>. Define <math>f(x)=x\{x\}</math>, and let <math>N</math> be the number of real-valued solutions to the equation <math>f(f(f(x)))=17</math> for <math>0\leq x\leq 2020</math>. Find the remainder when <math>N</math> is divided by <math>1000</math>. |
==Solution 1== | ==Solution 1== | ||
− | + | It's not too hard to see that, <math>N</math> is | |
+ | <cmath> | ||
\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} 1 | ||
− | . | + | .</cmath> |
− | + | One can see an easy combinatorical argument exists which is the official solution, but I will present another solution here for the sake of variety. | |
Applying algebraic manipulation and the hockey-stick identity <math>3</math> times gives | Applying algebraic manipulation and the hockey-stick identity <math>3</math> times gives | ||
− | + | ||
+ | <cmath> | ||
\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} 1 | ||
− | =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} \binom{z-y}{0} | + | </cmath> |
− | =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \binom{2020-y}{1} | + | |
− | =\sum_{x=17}^{2019} \binom{2021-x}{2} | + | <cmath> |
+ | =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} \binom{z-y}{0} | ||
+ | </cmath> | ||
+ | |||
+ | <cmath> | ||
+ | =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \binom{2020-y}{1} | ||
+ | </cmath> | ||
+ | |||
+ | <cmath> | ||
+ | =\sum_{x=17}^{2019} \binom{2021-x}{2} | ||
+ | </cmath> | ||
+ | |||
+ | <cmath> | ||
=\binom{2005}{3} | =\binom{2005}{3} | ||
− | \ | + | </cmath> |
+ | |||
+ | Hence, <cmath>N = \frac{2005 \cdot 2004 \cdot 2003}{3 \cdot 2\cdot 1} \equiv 10 (\mathrm{mod} \hskip .2cm 1000)</cmath> | ||
+ | |||
==Solution 2== | ==Solution 2== | ||
To solve <math>f(f(f(x)))=17</math>, we need to solve <math>f(x) = y</math> where <math>f(f(y))=17</math>, and to solve that we need to solve <math>f(y) = z</math> where <math>f(z) = 17</math>. | To solve <math>f(f(f(x)))=17</math>, we need to solve <math>f(x) = y</math> where <math>f(f(y))=17</math>, and to solve that we need to solve <math>f(y) = z</math> where <math>f(z) = 17</math>. | ||
− | It is clear to see for some integer <math>a \geq 17</math> there is exactly one value of <math>z</math> in the interval <math>[a, a+1)</math> where <math>f(z) = 17</math> To understand this, imagine the graph of <math>f(z)</math> on the interval <math>[a, a+1)</math> The graph starts at <math>0</math>, is continuous and increasing, and approaches <math>a+1</math>. So as long as <math>a+1 > 17</math>, there will be a solution for <math>z</math> in the interval. | + | It is clear to see for some integer <math>a \geq 17</math> there is exactly one value of <math>z</math> in the interval <math>[a, a+1)</math> where <math>f(z) = 17</math>. To understand this, imagine the graph of <math>f(z)</math> on the interval <math>[a, a+1)</math> The graph starts at <math>0</math>, is continuous and increasing, and approaches <math>a+1</math>. So as long as <math>a+1 > 17</math>, there will be a solution for <math>z</math> in the interval. |
− | Using this logic, we can find the number of solutions to <math>f(x) = y</math>. For every interval <math>[a, a+1)</math> where <math>a \geq \left \lfloor{y}\right \rfloor </math> there will be one solution for x in that interval. However, the question states <math>0 \leq x \leq 2020</math>, but because <math>x=2020</math> doesn't work we can change it to <math>0 \leq x < 2020</math>. Therefore, <math>\left \lfloor{y}\right \rfloor \leq a \leq 2019</math>, and there are <math>2020 - \left \lfloor{y}\right \rfloor</math> solutions to <math>f(x) = y</math>. | + | Using this logic, we can find the number of solutions to <math>f(x) = y</math>. For every interval <math>[a, a+1)</math> where <math>a \geq \left \lfloor{y}\right \rfloor </math> there will be one solution for <math>x</math> in that interval. However, the question states <math>0 \leq x \leq 2020</math>, but because <math>x=2020</math> doesn't work we can change it to <math>0 \leq x < 2020</math>. Therefore, <math>\left \lfloor{y}\right \rfloor \leq a \leq 2019</math>, and there are <math>2020 - \left \lfloor{y}\right \rfloor</math> solutions to <math>f(x) = y</math>. |
We can solve <math>f(y) = z</math> similarly. <math>0 \leq y < 2020</math> to satisfy the bounds of <math>x</math>, so there are <math>2020 - \left \lfloor{z}\right \rfloor</math> solutions to <math>f(y) = z</math>, and <math>0 \leq z < 2020</math> to satisfy the bounds of <math>y</math>. | We can solve <math>f(y) = z</math> similarly. <math>0 \leq y < 2020</math> to satisfy the bounds of <math>x</math>, so there are <math>2020 - \left \lfloor{z}\right \rfloor</math> solutions to <math>f(y) = z</math>, and <math>0 \leq z < 2020</math> to satisfy the bounds of <math>y</math>. | ||
Line 38: | Line 55: | ||
~aragornmf | ~aragornmf | ||
− | ==Solution | + | ==Solution 3 (Official MAA)== |
For any nonnegative integer <math>n</math>, the function <math>f</math> increases on the interval <math>[n,n+1)</math>, with <math>f(n)=0</math> and <math>f(x)<n+1</math> for every <math>x</math> in this interval. On this interval <math>f(x)=x(x-n)</math>, which takes on every real value in the interval <math>[0,n+1)</math> exactly once. Thus for each nonnegative real number <math>y</math>, the equation <math>f(x) = y</math> has exactly one solution <math>x \in [n, n+1)</math> for every <math>n \ge \lfloor y \rfloor</math>. | For any nonnegative integer <math>n</math>, the function <math>f</math> increases on the interval <math>[n,n+1)</math>, with <math>f(n)=0</math> and <math>f(x)<n+1</math> for every <math>x</math> in this interval. On this interval <math>f(x)=x(x-n)</math>, which takes on every real value in the interval <math>[0,n+1)</math> exactly once. Thus for each nonnegative real number <math>y</math>, the equation <math>f(x) = y</math> has exactly one solution <math>x \in [n, n+1)</math> for every <math>n \ge \lfloor y \rfloor</math>. | ||
Line 45: | Line 62: | ||
Thus <math>f(f(f(x)))=17</math> has exactly one solution <math>x</math> with <math>0\leq x\leq 2020</math> for each triple of integers <math>(a,b,c)</math> with <math>17\leq a\leq b\leq c<2020</math>, noting that <math>x=2020</math> is not a solution. This nondecreasing ordered triple can be identified with a multiset of three elements of the set of <math>2003</math> integers <math>\{17,18,19,\ldots,2019\}</math>, which can be selected in <math>\binom{2005}3</math> ways. Thus <cmath>N=\frac{2005\cdot 2004\cdot 2003}{6}\equiv 10\hskip -.2cm \pmod{1000}.</cmath> | Thus <math>f(f(f(x)))=17</math> has exactly one solution <math>x</math> with <math>0\leq x\leq 2020</math> for each triple of integers <math>(a,b,c)</math> with <math>17\leq a\leq b\leq c<2020</math>, noting that <math>x=2020</math> is not a solution. This nondecreasing ordered triple can be identified with a multiset of three elements of the set of <math>2003</math> integers <math>\{17,18,19,\ldots,2019\}</math>, which can be selected in <math>\binom{2005}3</math> ways. Thus <cmath>N=\frac{2005\cdot 2004\cdot 2003}{6}\equiv 10\hskip -.2cm \pmod{1000}.</cmath> | ||
− | ==Video Solution== | + | ==Video Solution 1== |
https://youtu.be/bz5N-jI2e0U?t=515 | https://youtu.be/bz5N-jI2e0U?t=515 | ||
+ | |||
+ | ==Video Solution 2== | ||
+ | https://youtu.be/YWKlWuwDwmI | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2020|n=II|num-b=13|num-a=15}} | {{AIME box|year=2020|n=II|num-b=13|num-a=15}} | ||
+ | [[Category: Intermediate Algebra Problems]] | ||
+ | [[Category: Functional Equation Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 12:25, 12 August 2020
Contents
Problem
For a 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
It's not too hard to see that, is One can see an easy combinatorical argument exists which is the official solution, but I will present another solution here for the sake of variety.
Applying algebraic manipulation and the hockey-stick identity times gives
Hence,
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 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 3 (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 1
https://youtu.be/bz5N-jI2e0U?t=515
Video Solution 2
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.