Difference between revisions of "2020 AIME II Problems/Problem 14"
m (→Solution) |
(→Solution) |
||
Line 23: | Line 23: | ||
~aragornmf | ~aragornmf | ||
+ | |||
+ | ==Solution 2 (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== | ==Video Solution== |
Revision as of 12:40, 18 June 2020
Problem
For 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
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 x 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 2 (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
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.