Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2020 AIME II Problems/Problem 14"

(→‎Video Solution)
(→‎Solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
 +
 +
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 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>.
 +
 +
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>
  
 
==Video Solution==
 
==Video Solution==

Revision as of 19:29, 12 June 2020

Problem

For real number $x$ let $\lfloor x\rfloor$ be the greatest integer less than or equal to $x$, and define $\{x\} = x - \lfloor x \rfloor$ to be the fractional part of $x$. For example, $\{3\} = 0$ and $\{4.56\} = 0.56$. Define $f(x)=x\{x\}$, and let $N$ be the number of real-valued solutions to the equation $f(f(f(x)))=17$ for $0\leq x\leq 2020$. Find the remainder when $N$ is divided by $1000$.

Solution

To solve $f(f(f(x)))=17$, we need to solve $f(x) = y$ where $f(f(y))=17$, and to solve that we need to solve $f(y) = z$ where $f(z) = 17$.

It is clear to see for some integer $a \geq 17$ there is exactly one value of $z$ in the interval $[a, a+1)$ where $f(z) = 17$ To understand this, imagine the graph of $f(z)$ on the interval $[a, a+1)$ The graph starts at $0$, is continuous and increasing, and approaches $a+1$. So as long as $a+1 > 17$, there will be a solution for $z$ in the interval.

Using this logic, we can find the number of solutions to $f(x) = y$. For every interval $[a, a+1)$ where $a \geq \left \lfloor{y}\right \rfloor$ there will be one solution for x in that interval. However, the question states $0 \leq x \leq 2020$, but because $x=2020$ doesn't work we can change it to $0 \leq x < 2020$. Therefore, $\left \lfloor{y}\right \rfloor \leq a \leq 2019$, and there are $2020 - \left \lfloor{y}\right \rfloor$ solutions to $f(x) = y$.

We can solve $f(y) = z$ similarly. $0 \leq y < 2020$ to satisfy the bounds of $x$, so there are $2020 - \left \lfloor{z}\right \rfloor$ solutions to $f(y) = z$, and $0 \leq z < 2020$ to satisfy the bounds of $y$.

Going back to $f(z) = 17$, there is a single solution for z in the interval $[a, a+1)$, where $17 \leq a \leq 2019$. (We now have an upper bound for $a$ because we know $z < 2020$.) There are $2003$ solutions for $z$, and the floors of these solutions create the sequence $17, 18, 19, ..., 2018, 2019$

Lets first look at the solution of $z$ where $\left \lfloor{z}\right \rfloor = 17$. Then $f(y) = z$ would have $2003$ solutions, and the floors of these solutions would also create the sequence $17, 18, 19, ..., 2018, 2019$.

If we used the solution of $y$ where $\left \lfloor{y}\right \rfloor = 17$, there would be $2003$ solutions for $f(x) = y$. If we used the solution of $y$ where $\left \lfloor{y}\right \rfloor = 18$, there would be $2002$ solutions for $x$, and so on. So for the solution of $z$ where $\left \lfloor{z}\right \rfloor = 17$, there will be $2003 + 2002 + 2001 + ... + 2 + 1 = \binom{2004}{2}$ solutions for $x$

If we now look at the solution of $z$ where $\left \lfloor{z}\right \rfloor = 18$, there would be $\binom{2003}{2}$ solutions for $x$. If we looked at the solution of $z$ where $\left \lfloor{z}\right \rfloor = 19$, there would be $\binom{2002}{2}$ solutions for $x$, and so on.

The total number of solutions to $x$ is $\binom{2004}{2} + \binom{2003}{2} + \binom{2002}{2} + ... + \binom{3}{2} + \binom{2}{2}$. Using the hockey stick theorem, we see this equals $\binom{2005}{3}$, and when we take the remainder of that number when divided by $1000$, we get the answer, $\boxed{10}$

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_14&oldid=125309"