Difference between revisions of "2020 AIME II Problems/Problem 14"
Topnotchmath (talk | contribs) m |
Mathkiddie (talk | contribs) |
||
(28 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
+ | 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== | ||
+ | Note that the upper bound for our sum is <math>2019,</math> and not <math>2020,</math> because if it were <math>2020</math> then the function composition cannot equal to <math>17.</math> From there, it's not too hard to see that, by observing the function composition from right to left, <math>N</math> is (note that the summation starts from the right to the left): | ||
+ | <cmath> | ||
+ | \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 | ||
+ | |||
+ | <cmath> | ||
+ | \sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} 1 | ||
+ | </cmath> | ||
+ | |||
+ | <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} | ||
+ | </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== | ||
+ | |||
+ | 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. | ||
+ | |||
+ | 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>. | ||
+ | |||
+ | Going back to <math>f(z) = 17</math>, there is a single solution for z in the interval <math>[a, a+1)</math>, where <math>17 \leq a \leq 2019</math>. (We now have an upper bound for <math>a</math> because we know <math>z < 2020</math>.) There are <math>2003</math> solutions for <math>z</math>, and the floors of these solutions create the sequence <math>17, 18, 19, ..., 2018, 2019</math> | ||
+ | |||
+ | Lets first look at the solution of <math>z</math> where <math>\left \lfloor{z}\right \rfloor = 17</math>. Then <math>f(y) = z</math> would have <math>2003</math> solutions, and the floors of these solutions would also create the sequence <math>17, 18, 19, ..., 2018, 2019</math>. | ||
+ | |||
+ | If we used the solution of <math>y</math> where <math>\left \lfloor{y}\right \rfloor = 17</math>, there would be <math>2003</math> solutions for <math>f(x) = y</math>. If we used the solution of <math>y</math> where <math>\left \lfloor{y}\right \rfloor = 18</math>, there would be <math>2002</math> solutions for <math>x</math>, and so on. So for the solution of <math>z</math> where <math>\left \lfloor{z}\right \rfloor = 17</math>, there will be <math>2003 + 2002 + 2001 + ... + 2 + 1 = \binom{2004}{2}</math> solutions for <math>x</math> | ||
+ | |||
+ | If we now look at the solution of <math>z</math> where <math>\left \lfloor{z}\right \rfloor = 18</math>, there would be <math>\binom{2003}{2}</math> solutions for <math>x</math>. If we looked at the solution of <math>z</math> where <math>\left \lfloor{z}\right \rfloor = 19</math>, there would be <math>\binom{2002}{2}</math> solutions for <math>x</math>, and so on. | ||
+ | |||
+ | The total number of solutions to <math>x</math> is <math>\binom{2004}{2} + \binom{2003}{2} + \binom{2002}{2} + ... + \binom{3}{2} + \binom{2}{2}</math>. Using the hockey stick theorem, we see this equals <math>\binom{2005}{3}</math>, and when we take the remainder of that number when divided by <math>1000</math>, we get the answer, <math>\boxed{10}</math> | ||
+ | |||
+ | ~aragornmf | ||
+ | |||
+ | ==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 each integer <math>a\geq 17</math> there is exactly one <math>x</math> with <math>\lfloor x\rfloor=a</math> such that <math>f(x)=17</math>; likewise for each integer <math>b\geq a\geq 17</math> there is exactly one <math>x</math> with <math>\lfloor f(x)\rfloor=a</math> and <math>\lfloor x\rfloor=b</math> such that <math>f(f(x))=17</math>. Finally, for each integer <math>c \ge b \ge a \ge 17</math> there is exactly one <math>x</math> with <math>\lfloor f(f(x)) \rfloor = a</math>, <math>\lfloor f(x)\rfloor=b</math>, and <math>\lfloor x\rfloor=c</math> such that <math>f(f(f(x)))=17</math>. | ||
+ | |||
+ | 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 1== | ||
+ | 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 14:31, 5 January 2024
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
Note that the upper bound for our sum is and not because if it were then the function composition cannot equal to From there, it's not too hard to see that, by observing the function composition from right to left, is (note that the summation starts from the right to the left): 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.