Difference between revisions of "2016 AMC 10B Problems/Problem 25"
Aaravdodhia (talk | contribs) (→Solution 1) |
Aaravdodhia (talk | contribs) (→Solution 1) |
||
Line 33: | Line 33: | ||
'''Explanation:''' | '''Explanation:''' | ||
− | Arrange all such fractions in increasing order and take a current <math>\frac{m}{n}</math> to study. Let <math>p</math> denote the previous fraction in the list and <math>x_\text{old}</math> (<math>0 \le x_\text{old} < k</math> for each <math>k</math>) be the largest so <math>\frac{x_\text{old}}{k} | + | Arrange all such fractions in increasing order and take a current <math>\frac{m}{n}</math> to study. Let <math>p</math> denote the previous fraction in the list and <math>x_\text{old}</math> (<math>0 \le x_\text{old} < k</math> for each <math>k</math>) be the largest so that <math>\frac{x_\text{old}}{k} \le p</math>. Since <math>\frac{m}{n} > p</math>, we clearly have all <math>x_\text{new} >= x_\text{old}</math>. Therefore, the change must be nonnegative. |
− | But among all numerators | + | But among all numerators cpprime to <math>n</math>, <math>m</math> is the largest. Therefore, choosing <math>\frac{m}{n}</math> as <math>{x}</math> creates a positive change in the term <math>\lfloor n \{ x \} \rfloor</math>. Since the overall change in <math>f(x)</math> increases as the fractions <math>m/n</math> increase, we deduce that all such fractions correspond to different values of the function. |
==Solution 2== | ==Solution 2== |
Revision as of 00:51, 28 December 2020
Contents
Problem
Let , where
denotes the greatest integer less than or equal to
. How many distinct values does
assume for
?
Solution 1
Since , we have
The function can then be simplified into
which becomes
We can see that for each value of ,
can equal integers from
to
.
Clearly, the value of changes only when
is equal to any of the fractions
.
So we want to count how many distinct fractions less than have the form
where
. Explanation for this is provided below. We can find this easily by computing
where is the Euler Totient Function. Basically
counts the number of fractions with
as its denominator (after simplification). This comes out to be
.
Because the value of is at least
and can increase
times, there are a total of
different possible values of
.
Explanation:
Arrange all such fractions in increasing order and take a current to study. Let
denote the previous fraction in the list and
(
for each
) be the largest so that
. Since
, we clearly have all
. Therefore, the change must be nonnegative.
But among all numerators cpprime to ,
is the largest. Therefore, choosing
as
creates a positive change in the term
. Since the overall change in
increases as the fractions
increase, we deduce that all such fractions correspond to different values of the function.
Solution 2
so we have
Clearly, the value of
changes only when
is equal to any of the fractions
. To get all the fractions, Graphing this function gives us
different fractions but on an average,
in each of the
intervals don’t work. This means there are a total of
different possible values of
.
See Also
2016 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.