Difference between revisions of "1985 AIME Problems/Problem 10"
(→Solution 6) |
Jeffersonj (talk | contribs) (→Solution 2 Shortcut Shortcut) |
||
(26 intermediate revisions by 6 users not shown) | |||
Line 6: | Line 6: | ||
where <math>x</math> is a [[real number]], and <math>\lfloor z \rfloor</math> denotes the greatest [[integer]] less than or equal to <math>z</math>? | where <math>x</math> is a [[real number]], and <math>\lfloor z \rfloor</math> denotes the greatest [[integer]] less than or equal to <math>z</math>? | ||
__TOC__ | __TOC__ | ||
− | |||
− | |||
− | + | == Solution 1 == | |
Noting that all of the numbers are even, we can reduce this to any real number <math>x</math> between <math>0</math> to <math>\frac 12</math>, as this will be equivalent to <math>\frac n2</math> to <math>\frac {n+1}2</math> for any integer <math>n</math> (same reasoning as above). So now we only need to test every 10 numbers; and our answer will be 100 times the number of integers we can reach between 1 and 10. | Noting that all of the numbers are even, we can reduce this to any real number <math>x</math> between <math>0</math> to <math>\frac 12</math>, as this will be equivalent to <math>\frac n2</math> to <math>\frac {n+1}2</math> for any integer <math>n</math> (same reasoning as above). So now we only need to test every 10 numbers; and our answer will be 100 times the number of integers we can reach between 1 and 10. | ||
Line 25: | Line 23: | ||
Out of these 6 cases, only 3 fails. So between 1 and 10 we can reach only the integers <math>1,2,4,5,6,10</math>; hence our solution is <math>6 \cdot 100 = \boxed{600}</math>. | Out of these 6 cases, only 3 fails. So between 1 and 10 we can reach only the integers <math>1,2,4,5,6,10</math>; hence our solution is <math>6 \cdot 100 = \boxed{600}</math>. | ||
− | + | == Solution 2 == | |
As we change the value of <math>x</math>, the value of our [[expression]] changes only when <math>x</math> crosses [[rational number]] of the form <math>\frac{m}{n}</math>, where <math>n</math> is divisible by 2, 4, 6 or 8. Thus, we need only see what happens at the numbers of the form <math>\frac{m}{\textrm{lcm}(2, 4, 6, 8)} = \frac{m}{24}</math>. This gives us 24 calculations to make; we summarize the results here: | As we change the value of <math>x</math>, the value of our [[expression]] changes only when <math>x</math> crosses [[rational number]] of the form <math>\frac{m}{n}</math>, where <math>n</math> is divisible by 2, 4, 6 or 8. Thus, we need only see what happens at the numbers of the form <math>\frac{m}{\textrm{lcm}(2, 4, 6, 8)} = \frac{m}{24}</math>. This gives us 24 calculations to make; we summarize the results here: | ||
Line 62: | Line 60: | ||
~[[User:N828335|N828335]] | ~[[User:N828335|N828335]] | ||
− | ===Solution 3=== | + | ===Solution 2 Bigger Shortcut (Close to Solution 6)=== |
+ | We only need to check the numbers where it increments, namely <math>\frac{1}{8}, \frac{1}{6}, \frac{1}{4}, \frac{1}{3}, \frac{3}{8}, \frac{1}{2}</math>. As shown before, we hit 6 integers (<math>1,2,4,5,6,10</math>) from <math>\frac{1}{24}</math> to <math>\frac{1}{2}</math>. Similarly, this should repeat 100 times, for <math>\boxed{600}</math> | ||
+ | |||
+ | ~JeffersonJ | ||
+ | |||
+ | ==Solution 3== | ||
Recall from Hermite's Identity that <math>\sum_{k = 0}^{n - 1}\left\lfloor x + \frac kn\right\rfloor = \lfloor nx\rfloor</math>. Then we can rewrite <math>\lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 6x \rfloor + \lfloor 8x \rfloor = 4\lfloor x\rfloor + \left\lfloor x + \frac18\right\rfloor + \left\lfloor x + \frac16\right\rfloor + 2\left\lfloor x + \frac14\right\rfloor + \left\lfloor x + \frac13\right\rfloor</math> | Recall from Hermite's Identity that <math>\sum_{k = 0}^{n - 1}\left\lfloor x + \frac kn\right\rfloor = \lfloor nx\rfloor</math>. Then we can rewrite <math>\lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 6x \rfloor + \lfloor 8x \rfloor = 4\lfloor x\rfloor + \left\lfloor x + \frac18\right\rfloor + \left\lfloor x + \frac16\right\rfloor + 2\left\lfloor x + \frac14\right\rfloor + \left\lfloor x + \frac13\right\rfloor</math> | ||
<math>+ \left\lfloor x + \frac38\right\rfloor + 4\left\lfloor x + \frac12\right\rfloor + \left\lfloor x + \frac58\right\rfloor + \left\lfloor x + \frac23\right\rfloor + 2\left\lfloor x + \frac34\right\rfloor + \left\lfloor x + \frac56\right\rfloor + \left\lfloor x + \frac78\right\rfloor</math>. There are <math>12</math> terms here (we don't actually have to write all of it out; we can just see where there will be duplicates and subtract accordingly from <math>20</math>). Starting from every integer <math>x</math>, we can keep adding to achieve one higher value for each of these terms, but after raising the last term, we will have raised the whole sum by <math>20</math> while only achieving <math>12</math> of those <math>20</math> values. We can conveniently shift the <math>1000</math> (since it can be achieved) to the position of the <math>0</math> so that there are only complete cycles of <math>20</math>, and the answer is <math>\frac {12}{20}\cdot1000 = \boxed{600}</math>. | <math>+ \left\lfloor x + \frac38\right\rfloor + 4\left\lfloor x + \frac12\right\rfloor + \left\lfloor x + \frac58\right\rfloor + \left\lfloor x + \frac23\right\rfloor + 2\left\lfloor x + \frac34\right\rfloor + \left\lfloor x + \frac56\right\rfloor + \left\lfloor x + \frac78\right\rfloor</math>. There are <math>12</math> terms here (we don't actually have to write all of it out; we can just see where there will be duplicates and subtract accordingly from <math>20</math>). Starting from every integer <math>x</math>, we can keep adding to achieve one higher value for each of these terms, but after raising the last term, we will have raised the whole sum by <math>20</math> while only achieving <math>12</math> of those <math>20</math> values. We can conveniently shift the <math>1000</math> (since it can be achieved) to the position of the <math>0</math> so that there are only complete cycles of <math>20</math>, and the answer is <math>\frac {12}{20}\cdot1000 = \boxed{600}</math>. | ||
− | + | == Solution 4 == | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Let <math>x=\lfloor x\rfloor+\{x\}</math> then | Let <math>x=\lfloor x\rfloor+\{x\}</math> then | ||
Line 100: | Line 94: | ||
~ Nafer | ~ Nafer | ||
− | === Solution 6 === | + | == Solution 5 == |
+ | |||
+ | To simplify the question, let <math>y = 2x</math>. Then, the expression in the question becomes <math>\lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor</math>. | ||
+ | |||
+ | Let <math>\{x\}</math> represent the non-integer part of <math>x</math> (For example, <math>\{2.8\} = 0.8</math>). Then, | ||
+ | |||
+ | <cmath>\begin{align*} | ||
+ | \lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor &= y - \{y\} + 2y - \{2y\} + 3y - \{3y\} + 4y - \{4y\} \\ | ||
+ | &= 10y - (\{y\} + \{2y\} + \{3y\} + \{4y\}) \\ | ||
+ | &= 10(\lfloor y \rfloor + \{y\}) - (\{y\} + \{2y\} + \{3y\} + \{4y\}) \\ | ||
+ | &= 10\lfloor y \rfloor + 10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\}) \\ | ||
+ | &= 10\lfloor y \rfloor + 9\{y\} - (\{2y\} + \{3y\} + \{4y\}) \\ | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | Since <math>\lfloor y \rfloor</math> is always an integer, <math>10\lfloor y \rfloor</math> will be a multiple of 10. Thus, we look for the range of the other part of the expression. We will be able to reach the same numbers when <math>y</math> ranges from <math>0</math> to <math>1</math>, because the curly brackets (<math>\{\}</math>) gets rid of any integer part. Let the combined integer part of <math>2y</math>, <math>3y</math>, and <math>4y</math> be <math>k</math> (In other words, <math>k = \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor</math>). Then, | ||
+ | |||
+ | <cmath>\begin{align*} | ||
+ | 9\{y\} - (\{2y\} + \{3y\} + \{4y\}) &= 9\{y\} - (2\{y\} + 3\{y\} + 4\{y\} - k) \\ | ||
+ | &= 9\{y\} - (9\{y\} - k) \\ | ||
+ | &= k | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | The maximum value of <math>k</math> will be when <math>y</math> is slightly less than <math>1</math>, which means <math>k = 1 + 2 + 3 = 6</math>. As <math>y</math> increases from <math>0</math> to <math>1</math>, <math>k</math> will increase whenever <math>2y</math>, <math>3y</math>, or <math>4y</math> is an integer, which happens when <math>y</math> hits one of the numbers in the set <math>\left\{\dfrac14, \dfrac13, \dfrac12, \dfrac23, \dfrac34 \right\}</math>. When <math>y</math> reaches <math>\dfrac12</math>, both <math>2y</math> and <math>4y</math> will be an integer, so <math>k</math> will increase by <math>2</math>. For all the other numbers in the set, <math>k</math> increases by <math>1</math> since only <math>1</math> number in the set will be an integer. Thus, the possible values of <math>k</math> are <math>\{0, 1, 2, 4, 5, 6\}</math>. | ||
+ | |||
+ | Finally, looking back at the original expression, we plug in <math>k</math> to get a multiple of <math>10</math> plus any number in <math>\{0, 1, 2, 4, 5, 6\}</math>. Thus, we hit all numbers ending in <math>\{0, 1, 2, 4, 5, 6\}</math>, of which there are <math>\boxed{600}</math>. | ||
+ | |||
+ | ~Owen1204 | ||
+ | |||
+ | ==Solution 6== | ||
+ | |||
+ | Imagine that we gradually increase <math>x</math> from <math>0</math> to <math>1</math>. At the beginning, the value of our expression is <math>0</math>, at the end it is <math>2+4+6+8=20</math>. Note that every time <math>x=\frac{a}{b}</math> for some positive integer <math>a</math> and a positive multiple <math>b</math> of either <math>2, 4, 6,</math> or <math>8</math>. Thus, we have been able to express 12 of the integers from 1 through 20 when <math>0<x<1</math>, namely when <cmath>x = \frac{1}{2}, \frac{2}{2}=1, \frac{1}{4}, \frac{3}{4}, \frac{1}{6}, \frac{1}{3}, \frac{2}{3}, \frac{5}{6}, \frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}</cmath>. | ||
− | |||
− | + | Notice that <cmath>\lfloor 2(x+n) \rfloor + \lfloor 4(x+n)\rfloor + \lfloor 6(x+n) \rfloor+ \lfloor8(x+n) \rfloor= \lfloor 2x \rfloor+ \lfloor 4x \rfloor+ \lfloor 6x \rfloor+ \lfloor 8x \rfloor+ 20n</cmath>. This conceptually means that the number of integers that can be expressed in the range <math>(i, j)</math> is the same as the number of integers that can be expressed in the range <math>(i+x, j+x)</math>. Thus, because we can express <math>12</math> integers in the range <math>(1, 20)</math>, we can cover <math>12*50 = \boxed{600}</math> from 1 to 1000. | |
+ | <math>-\text{thinker123}</math> | ||
− | + | ==Solution 7== | |
− | + | After observing, we can see that there are <math>6</math> values of can be evaluated through the expression every <math>10</math> numbers, so our answer is <math>6*100=600</math> ~bluesoul | |
== See also == | == See also == | ||
Line 117: | Line 141: | ||
* [[Mathematics competition resources]] | * [[Mathematics competition resources]] | ||
− | [[Category:Intermediate | + | [[Category:Intermediate Number Theory Problems]] |
Latest revision as of 18:16, 28 March 2022
Problem
How many of the first 1000 positive integers can be expressed in the form
,
where is a real number, and
denotes the greatest integer less than or equal to
?
Contents
Solution 1
Noting that all of the numbers are even, we can reduce this to any real number between
to
, as this will be equivalent to
to
for any integer
(same reasoning as above). So now we only need to test every 10 numbers; and our answer will be 100 times the number of integers we can reach between 1 and 10.
We can now approach this by directly searching for the integers (this solution) or brute forcing all of the cases (next solution):
We can match up the greatest integer functions with one of the partitions of the integer. If we let then we get the solution
; now consider when
:
,
,
,
. But according to this the maximum we can get is
, so we only need to try the first 6 numbers.
: Easily possible, for example try plugging in
.
: Also simple, for example using
.
: The partition must either be
or
. If
, then
, but then
; not possible; and vice versa to show that the latter partition doesn't work. So we cannot obtain
.
: We can partition as
, and from the previous case we see that
works.
: We can partition as
, from which we find that
works.
: We can partition as
, from which we find that
works.
Out of these 6 cases, only 3 fails. So between 1 and 10 we can reach only the integers ; hence our solution is
.
Solution 2
As we change the value of , the value of our expression changes only when
crosses rational number of the form
, where
is divisible by 2, 4, 6 or 8. Thus, we need only see what happens at the numbers of the form
. This gives us 24 calculations to make; we summarize the results here:
Thus, we hit 12 of the first 20 integers and so we hit of the first
.
Solution 2 Shortcut
Because are all multiples of
, we can speed things up. We only need to check up to
, and the rest should repeat. As shown before, we hit 6 integers (
) from
to
. Similarly, this should repeat 100 times, for
Solution 2 Bigger Shortcut (Close to Solution 6)
We only need to check the numbers where it increments, namely . As shown before, we hit 6 integers (
) from
to
. Similarly, this should repeat 100 times, for
~JeffersonJ
Solution 3
Recall from Hermite's Identity that . Then we can rewrite
. There are
terms here (we don't actually have to write all of it out; we can just see where there will be duplicates and subtract accordingly from
). Starting from every integer
, we can keep adding to achieve one higher value for each of these terms, but after raising the last term, we will have raised the whole sum by
while only achieving
of those
values. We can conveniently shift the
(since it can be achieved) to the position of the
so that there are only complete cycles of
, and the answer is
.
Solution 4
Let then
Similar to the previous solutions, the value of
changes when
, where
,
. Using Euler's Totient Function
to obtain
different values for
. (note that here Euler's Totient Function counts the number of
where
,
are relatively prime so that the values of
won't overlap.).
Thus if can be expressed as
, then
for some non-negative integers
,
, where there are
values for
.
Exclusively, there are values for
in the range
, or
ordered pairs
.
If ,
, which includes
ordered pairs.
If ,
, which includes
ordered pair.
In total, there are values for
.
~ Nafer
Solution 5
To simplify the question, let . Then, the expression in the question becomes
.
Let represent the non-integer part of
(For example,
). Then,
Since is always an integer,
will be a multiple of 10. Thus, we look for the range of the other part of the expression. We will be able to reach the same numbers when
ranges from
to
, because the curly brackets (
) gets rid of any integer part. Let the combined integer part of
,
, and
be
(In other words,
). Then,
The maximum value of will be when
is slightly less than
, which means
. As
increases from
to
,
will increase whenever
,
, or
is an integer, which happens when
hits one of the numbers in the set
. When
reaches
, both
and
will be an integer, so
will increase by
. For all the other numbers in the set,
increases by
since only
number in the set will be an integer. Thus, the possible values of
are
.
Finally, looking back at the original expression, we plug in to get a multiple of
plus any number in
. Thus, we hit all numbers ending in
, of which there are
.
~Owen1204
Solution 6
Imagine that we gradually increase from
to
. At the beginning, the value of our expression is
, at the end it is
. Note that every time
for some positive integer
and a positive multiple
of either
or
. Thus, we have been able to express 12 of the integers from 1 through 20 when
, namely when
.
Notice that . This conceptually means that the number of integers that can be expressed in the range
is the same as the number of integers that can be expressed in the range
. Thus, because we can express
integers in the range
, we can cover
from 1 to 1000.
Solution 7
After observing, we can see that there are values of can be evaluated through the expression every
numbers, so our answer is
~bluesoul
See also
1985 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 9 |
Followed by Problem 11 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |