Difference between revisions of "2016 AMC 10B Problems/Problem 25"
(→Video Solution) |
m (→Solution 2) |
||
(21 intermediate revisions by 5 users not shown) | |||
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 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} \ge x_\text{old}</math>. Therefore, the change must be nonnegative. | + | 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>\text{ }\text{ }\frac{m}{n} > p</math>, we clearly have all <math>x_\text{new} \ge x_\text{old}</math>. Therefore, the change must be nonnegative. |
− | But among all numerators coprime to <math>n</math> so far, <math>m</math> is the largest. Therefore, choosing <math>\frac{m}{n}</math> as <math>{x}</math> increases the value <math>\lfloor n \{ x \} \rfloor</math>. Since the overall change in <math>f(x)</math> is positive as fractions <math>m/n</math> increase, we deduce that all such fractions correspond to different values of the function. | + | But among all numerators coprime to <math>n</math> so far, <math>m</math> is the largest. Therefore, choosing <math>\frac{m}{n}</math> as <math>{x}</math> increases the value <math>\lfloor n \{ x \} \rfloor</math>. Since the overall change in <math>f(x)</math> is positive as fractions <math>m/n</math> increase, we deduce that all such fractions correspond to different values of the function. |
+ | |||
+ | Minor Latex Edits made by MathWizard10. | ||
+ | |||
+ | ===Supplement=== | ||
+ | |||
+ | Here are all the distinct <math>\frac{m}{n}</math> and <math>\phi(k):</math> | ||
+ | |||
+ | When <math>n=2</math> , <math>\frac{m}{n}=\frac{1}{2}</math> . <math>\phi(2)=1</math> | ||
+ | |||
+ | When <math>n=3</math> , <math>\frac{m}{n}=\frac{1}{3}</math> , <math>\frac{2}{3}</math> . <math>\phi(3)=2</math> | ||
+ | |||
+ | When <math>n=4</math> , <math>\frac{m}{n}=\frac{1}{4}</math> , <math>\frac{3}{4}</math> . <math>\phi(4)=2</math> | ||
+ | |||
+ | When <math>n=5</math> , <math>\frac{m}{n}=\frac{1}{5}</math> , <math>\frac{2}{5}</math> , <math>\frac{3}{5}</math> , <math>\frac{4}{5}</math> . <math>\phi(5)=4</math> | ||
+ | |||
+ | When <math>n=6</math> , <math>\frac{m}{n}=\frac{1}{6}</math> , <math>\frac{5}{6}</math> . <math>\phi(6)=2</math> | ||
+ | |||
+ | When <math>n=7</math> , <math>\frac{m}{n}=\frac{1}{7}</math> , <math>\frac{2}{7}</math> , <math>\frac{3}{7}</math> , <math>\frac{4}{7}</math> , <math>\frac{5}{7}</math> , <math>\frac{6}{7}</math> . <math>\phi(7)=6</math> | ||
+ | |||
+ | When <math>n=8</math> , <math>\frac{m}{n}=\frac{1}{8}</math> , <math>\frac{3}{8}</math> , <math>\frac{5}{8}</math> , <math>\frac{7}{8}</math> . <math>\phi(8)=4</math> | ||
+ | |||
+ | When <math>n=9</math> , <math>\frac{m}{n}=\frac{1}{9}</math> , <math>\frac{2}{9}</math> , <math>\frac{4}{9}</math> , <math>\frac{5}{9}</math> , <math>\frac{7}{9}</math> , <math>\frac{8}{9}</math> . <math>\phi(9)=6</math> | ||
+ | |||
+ | When <math>n=10</math> , <math>\frac{m}{n}=\frac{1}{10}</math> , <math>\frac{3}{10}</math> , <math>\frac{7}{10}</math> , <math>\frac{9}{10}</math> . <math>\phi(10)=4</math> | ||
+ | |||
+ | <math>\sum_{k=2}^{10} \phi(k)=31</math> | ||
+ | |||
+ | <math>31+1=\fbox{\textbf{(A)}\ 32}</math> | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
==Solution 2== | ==Solution 2== | ||
− | <math>x = \lfloor x \rfloor + \{ x \}</math> so we have <cmath>f(x) = \sum_{k=2}^{10} \lfloor k \{ x \} \rfloor.</cmath> Clearly, the value of <math>\lfloor k \{ x \} \rfloor</math> changes only when <math>x</math> is equal to any of the fractions <math>\frac{1}{k}, \frac{2}{k} \dots \frac{k-1}{k}</math>. To get all the fractions, | + | <math>x = \lfloor x \rfloor + \{ x \}</math> so we have <cmath>f(x) = \sum_{k=2}^{10} \lfloor k \{ x \} \rfloor.</cmath> Clearly, the value of <math>\lfloor k \{ x \} \rfloor</math> changes only when <math>x</math> is equal to any of the fractions <math>\frac{1}{k}, \frac{2}{k} \dots \frac{k-1}{k}</math>. To get all the fractions, graphing this function gives us <math>46</math> different fractions. But on average, about one is every three fractions are repetitions of another fraction (see below). This means there are a total of <math>\fbox{\textbf{(A)}\ 32}</math> different possible values of <math>f(x)</math>. |
+ | |||
+ | Note: This is because all fractions with denominators <math>2\le k \le 5</math> are repetitions of another fraction with denominator <math>2k,</math> which is about <math>\frac{1}{4}</math> of all the fractions. Also, some other repeated fractions are scattered around the fractions with higher denominators. This means that we can safely estimate that about <math>\frac{1}{3}</math> of the fractions are repetitions of another fraction. | ||
+ | |||
+ | ==Solution 3 (Casework)== | ||
+ | |||
+ | Solution <math>1</math> is abstract. In this solution I will give a concrete explanation. | ||
+ | |||
+ | WLOG, for example, when <math>x</math> increases from <math>\frac{2}{3}-\epsilon</math> to <math>\frac{2}{3}</math>, <math>\lfloor 3 \{ x \} \rfloor</math> will increase from <math>1</math> to <math>2</math>, <math>\lfloor 6 \{ x \} \rfloor</math> will increase from <math>3</math> to <math>4</math>, <math>\lfloor 9 \{ x \} \rfloor</math> will increase from <math>5</math> to <math>6</math>. In total, <math>f(x)</math> will increase by <math>3</math>. Because <math>\frac{1}{3}=\frac{2}{6}=\frac{3}{9}</math>, these <math>3</math> numbers are actually <math>1</math> distinct number to cause <math>f(x)</math> to change. In general, when <math>x</math> increases from <math>\frac{m}{n}-\epsilon</math> to <math>\frac{m}{n}</math>, <math>\lfloor k \{ x \} \rfloor</math> will increse from <math>k \cdot \frac{m}{n} -1</math> to <math>k \cdot \frac{m}{n} </math> if <math>k \cdot \frac{m}{n} </math> is an integer, and the value of <math>f(x)</math> will change. So the total number of distinct values <math>f(x)</math> could take is equal to the number of distinct values of <math>\frac{m}{n}</math>, where <math>0 < \frac{m}{n}<1</math> and <math>2 \le n \le 10</math>. | ||
+ | |||
+ | Solution <math>1</math> uses Euler Totient Function to count the distinct number of <math>\frac{m}{n}</math>, I am going to use casework to count the distinct values of <math>\frac{m}{n}</math> by not counting the duplicate ones. | ||
+ | |||
+ | When <math>n=10</math> , <math>\frac{m}{n}=\frac{1}{10}</math> , <math>\frac{2}{10}</math> , <math>...</math> , <math>\frac{9}{10}</math> <math>\Longrightarrow 9</math> | ||
+ | |||
+ | When <math>n=9</math> , <math>\frac{m}{n}=\frac{1}{9}</math> , <math>\frac{2}{9}</math> , <math>...</math> , <math>\frac{8}{9}</math> <math>\Longrightarrow 8</math> | ||
+ | |||
+ | When <math>n=8</math> , <math>\frac{m}{n}=\frac{1}{8}</math> , <math>\frac{2}{8}</math> , <math>...</math> , <math>\frac{7}{8}</math> <math>\Longrightarrow 6</math> ( <math>\frac{4}{8}</math> is duplicate) | ||
+ | |||
+ | When <math>n=7</math> , <math>\frac{m}{n}=\frac{1}{7}</math> , <math>\frac{2}{7}</math> , <math>...</math> , <math>\frac{6}{7}</math> <math>\Longrightarrow 6</math> | ||
+ | |||
+ | When <math>n=6</math> , <math>\frac{m}{n}=\frac{1}{6}</math> , <math>\frac{5}{6}</math> <math>\Longrightarrow 2</math> ( <math>\frac{2}{6}</math> , <math>\frac{3}{6}</math> , and <math>\frac{4}{6}</math> is duplicate) | ||
+ | |||
+ | When <math>n=5</math>, <math>4</math>, <math>3</math>, <math>2</math>, all the <math>\frac{m}{n}</math> is duplicate. | ||
+ | |||
+ | <math>9+8+6+6+2=31</math>, <math>31+1=\fbox{\textbf{(A)}\ 32}</math> | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
+ | |||
+ | ==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*} | ||
+ | \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}\sum_{i=1}^{k-1}( \lfloor x + \frac{i}{k} \rfloor - \lfloor x \rfloor)\\ | ||
+ | &= \sum_{k=2}^{10}\sum_{i=1}^{k-1}( \lfloor \{ x \} + \frac{i}{k} \rfloor) | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | <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> | ||
+ | |||
+ | 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>, | ||
+ | <cmath>\lfloor \{ x \} + \frac{i_j}{k_j} \rfloor = 1</cmath> | ||
+ | |||
+ | if <math>j > n </math>, | ||
+ | <cmath>\lfloor \{ x \} + \frac{i_j}{k_j} \rfloor = 0</cmath> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
+ | |||
+ | ==Solution 5 (No Euler Totient Function)== | ||
+ | |||
+ | Solution without the [[Euler Totient Function]] | ||
+ | |||
+ | Proceed in the same way as Solution 1 until you reach <cmath>f(x) = \sum_{k=2}^{10} \lfloor k \{ x \} \rfloor</cmath>. | ||
+ | |||
+ | We first count the case where all values of <math>\lfloor kx_f \rfloor</math> is 0. Now, notice that the value of <math>n/k</math> can take <math>k-1</math> values (excluding 0) since <math>n</math> must be strictly less than <math>k</math>. If we add up all <math>k-1</math> for <math>2<=k<=10</math>, we get <math>1+2+3+...+9 = 45</math>. | ||
+ | |||
+ | Some might be tempted to mark <math>45</math> or <math>46</math> now, but there can be repeating values. Notice that whenever the value of <math>(1/2)x_f</math> changes, the value of <math>(1/8)x_f</math> must change. This means that every case in <math>k=2</math> is covered by <math>k=8</math>. This is extended to every number that is a factor of another (3 and 9, 5 and 10). Therefore, we can eliminate <math>k=2,3,4,5</math> as they are all factors of other values of <math>k</math>, which eliminates 10 cases. | ||
+ | |||
+ | Within the remaining numbers, there are a couple of numbers that can still have repeating values. These are <math>(6, 9)</math>, <math>(6, 8)</math>, and <math>(8,10)</math>. The first one repeats when <math>n/k</math> is equal to <math>1/3</math> or <math>2/3</math>, eliminating 2 cases, and the second and third repeat whenever <math>n/k</math> is equal to <math>1/2</math>. This eliminates another 2 cases. | ||
+ | |||
+ | Therefore, our final answer is <math>45+1-10-2-2=32</math>, which is <math>\fbox{\textbf{(A)}\ 32}</math>. | ||
+ | |||
+ | ==Remark== | ||
+ | |||
+ | This problem is similar to [https://artofproblemsolving.com/wiki/index.php/1985_AIME_Problems/Problem_10 1985 AIME Problem 10]. Both problems use the [[Euler Totient Function]] to find the number of distinct values of <math>\lfloor k \{ x \} \rfloor</math>. | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
==Video Solution== | ==Video Solution== | ||
Line 47: | Line 158: | ||
{{AMC10 box|year=2016|ab=B|num-b=24|after=Last Problem}} | {{AMC10 box|year=2016|ab=B|num-b=24|after=Last Problem}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] |
Latest revision as of 18:23, 4 April 2023
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 MathWizard10.
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, about one is every three fractions are repetitions of another fraction (see below). This means there are a total of
different possible values of
.
Note: This is because all fractions with denominators are repetitions of another fraction with denominator
which is about
of all the fractions. Also, some other repeated fractions are scattered around the fractions with higher denominators. This means that we can safely estimate that about
of the fractions are repetitions of another fraction.
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
Solution 5 (No Euler Totient Function)
Solution without the Euler Totient Function
Proceed in the same way as Solution 1 until you reach .
We first count the case where all values of is 0. Now, notice that the value of
can take
values (excluding 0) since
must be strictly less than
. If we add up all
for
, we get
.
Some might be tempted to mark or
now, but there can be repeating values. Notice that whenever the value of
changes, the value of
must change. This means that every case in
is covered by
. This is extended to every number that is a factor of another (3 and 9, 5 and 10). Therefore, we can eliminate
as they are all factors of other values of
, which eliminates 10 cases.
Within the remaining numbers, there are a couple of numbers that can still have repeating values. These are ,
, and
. The first one repeats when
is equal to
or
, eliminating 2 cases, and the second and third repeat whenever
is equal to
. This eliminates another 2 cases.
Therefore, our final answer is , which 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.