|
|
| Line 1: |
Line 1: |
| − | ==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==
| |
| − | {{AIME box|year=2020|n=II|num-b=13|num-a=15}}
| |
| − | [[Category: Intermediate Algebra Problems]]
| |
| − | [[Category: Functional Equation Problems]]
| |
| − | {{MAA Notice}}
| |
