Difference between revisions of "2016 AMC 10B Problems/Problem 25"
Isabelchen (talk | contribs) m (→Solution 4) |
Isabelchen (talk | contribs) (→Solution 4) |
||
Line 97: | Line 97: | ||
==Solution 4== | ==Solution 4== | ||
− | + | By [https://en.wikipedia.org/wiki/Hermite%27s_identity Hermite's Identity], | |
− | + | <cmath>\begin{align*} | |
+ | & \lfloor kx \rfloor = \lfloor x \rfloor + \lfloor x + \frac1k \rfloor + \lfloor x + \frac2k \rfloor + \dots + \lfloor x + \frac{k-1}{k} \rfloor\\ | ||
+ | & \lfloor kx \rfloor -k \lfloor x \rfloor = \lfloor x + \frac1k \rfloor + \lfloor x + \frac2k \rfloor + \dots + \lfloor x + \frac{k-1}{k} \rfloor - (k-1) \lfloor x \rfloor | ||
+ | \end{align*}</cmath> | ||
+ | Therefore, | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
\sum_{k=2}^{10}(\lfloor kx \rfloor -k \lfloor x \rfloor) & \\ | \sum_{k=2}^{10}(\lfloor kx \rfloor -k \lfloor x \rfloor) & \\ | ||
&= \sum_{k=2}^{10}(\lfloor x + \frac1k \rfloor + \lfloor x + \frac2k \rfloor + \dots + \lfloor x + \frac{k-1}{k} \rfloor - (k-1) \lfloor x \rfloor)\\ | &= \sum_{k=2}^{10}(\lfloor x + \frac1k \rfloor + \lfloor x + \frac2k \rfloor + \dots + \lfloor x + \frac{k-1}{k} \rfloor - (k-1) \lfloor x \rfloor)\\ | ||
− | &= \sum_{k=2}^{10} | + | &= \sum_{k=2}^{10}\sum_{i=1}^{k-1}( \lfloor x + \frac{i}{k} \rfloor - \lfloor x \rfloor)\\ |
− | &= \sum_{k=2}^{10} | + | &= \sum_{k=2}^{10}\sum_{i=1}^{k-1}( \lfloor \{ x \} + \frac{i}{k} \rfloor) |
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | <math>{x} < 1</math>, <math>\frac{j}{k}<1</math> | + | <math>0 \le \{ x \} < 1</math>, <math>0 < \frac{j}{k}<1</math> <math>\Longrightarrow</math> <math>0 < \lfloor \{ x \} + \frac{i}{k} \rfloor < 2</math> <math>\Longrightarrow</math> <math>\lfloor \{ x \} + \frac{i}{k} \rfloor = 0 \text{ or } 1</math> |
+ | |||
+ | <math>\{ x \} + \frac{i}{k} \ge 1</math> <math>\Longrightarrow</math> <math>\{ x \} \ge 1 - \frac{j}{k}</math> | ||
− | <math>1 - \frac{i_n}{k_n} \le {x} < 1- \frac{ | + | Arrange <math>1 - \frac{i_j}{k_j}</math> from small to large, <math>\{ x \}</math> must fall in one interval. WLOG, suppose <math>1 - \frac{i_n}{k_n} \le \{ x \} < 1- \frac{i_{n+1}}{k_{n+1}}</math>. |
if <math>j \le n </math>, | if <math>j \le n </math>, | ||
Line 118: | Line 124: | ||
<cmath>\lfloor \{ x \} + \frac{i_j}{k_j} \rfloor = 0</cmath> | <cmath>\lfloor \{ x \} + \frac{i_j}{k_j} \rfloor = 0</cmath> | ||
− | Therefore, every distinct value <math>\sum_{k=2}^{10} | + | Therefore, every distinct value of <math>\sum_{k=2}^{10}\sum_{i=1}^{k-1}( \lfloor \{ x \} + \frac{i}{k} \rfloor)</math> has one to one correspondence with a distinct value of <math>\frac{i}{k}</math>, <math>\frac{i}{k}</math> is not reducible, <math>(i, k) = 1</math>. |
Using the [[Euler Totient Function]] as in [https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_10B_Problems/Problem_25#Supplement Solution 1's Supplement], the answer is <math>\fbox{\textbf{(A)}\ 32}</math> | Using the [[Euler Totient Function]] as in [https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_10B_Problems/Problem_25#Supplement Solution 1's Supplement], the answer is <math>\fbox{\textbf{(A)}\ 32}</math> |
Revision as of 05:46, 27 March 2022
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 coprime to so far, is the largest. Therefore, choosing as increases the value . Since the overall change in is positive as fractions increase, we deduce that all such fractions correspond to different values of the function.
Minor Latex Edits made by MATHWIZARD2010.
Supplement
Here are all the distinct and
When , .
When , , .
When , , .
When , , , , .
When , , .
When , , , , , , .
When , , , , .
When , , , , , , .
When , , , , .
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 average, in each of the intervals don’t work. This means there are a total of different possible values of .
Solution 3 (Casework)
Solution is abstract. In this solution I will give a concrete explanation.
WLOG, for example, when increases from to , will increase from to , will increase from to , will increase from to . In total, will increase by . Because , these numbers are actually distinct number to cause to change. In general, when increases from to , will increse from to if is an integer, and the value of will change. So the total number of distinct values could take is equal to the number of distinct values of , where and .
Solution uses Euler Totient Function to count the distinct number of , I am going to use casework to count the distinct values of by not counting the duplicate ones.
When , , , ,
When , , , ,
When , , , , ( is duplicate)
When , , , ,
When , , ( , , and is duplicate)
When , , , , all the is duplicate.
,
Solution 4
Therefore,
,
Arrange from small to large, must fall in one interval. WLOG, suppose .
if ,
if ,
Therefore, every distinct value of has one to one correspondence with a distinct value of , is not reducible, .
Using the Euler Totient Function as in Solution 1's Supplement, the answer is
Remark
This problem is similar to 1985 AIME Problem 10. Both problems use the Euler Totient Function to find the number of distinct values of .
Video Solution
https://www.youtube.com/watch?v=zXJrdDtZNbw
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.