Difference between revisions of "2020 AIME II Problems/Problem 14"
(→Solution 1) |
Mathkiddie (talk | contribs) |
||
(18 intermediate revisions by 6 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== | ||
− | + | 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> | <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 | ||
Line 10: | Line 10: | ||
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> | <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> | </cmath> | ||
+ | |||
<cmath> | <cmath> | ||
− | =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} \binom{z-y}{0} | + | =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \sum_{z=y}^{2019} \binom{z-y}{0} |
</cmath> | </cmath> | ||
+ | |||
<cmath> | <cmath> | ||
− | =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \binom{2020-y}{1} | + | =\sum_{x=17}^{2019} \sum_{y=x}^{2019} \binom{2020-y}{1} |
</cmath> | </cmath> | ||
+ | |||
<cmath> | <cmath> | ||
− | =\sum_{x=17}^{2019} \binom{2021-x}{2} | + | =\sum_{x=17}^{2019} \binom{2021-x}{2} |
</cmath> | </cmath> | ||
+ | |||
<cmath> | <cmath> | ||
=\binom{2005}{3} | =\binom{2005}{3} | ||
</cmath> | </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== | ||
Line 30: | Line 37: | ||
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 48: | 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 55: | 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 15: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.