Difference between revisions of "1985 AIME Problems/Problem 10"
(→Solution 6) |
|||
Line 104: | Line 104: | ||
First, let <math>y = 2x</math> to simplify the question. The expression in the question then becomes <math>\lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor</math>. | First, let <math>y = 2x</math> to simplify the question. The expression in the question then becomes <math>\lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor</math>. | ||
− | Let <math>\lfloor x\rfloor = x - \{x\}</math>. Then, <math>\lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor</math> can be rewritten as <math>y - \{y\} + 2y - \{2y\} + 3y - \{3y\} + 4y - \{4y\}</math>, or <math>10y - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math>. Substituting <math>\lfloor y\rfloor + \{y\}</math> for <math>y</math> yields <math>10\lfloor y\rfloor + 10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math>. Since <math>10\lfloor y\rfloor</math> will always be a multiple of <math>10</math>, we must find the range of <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math>. Clearly, <math>10\{y\}\in [0, 10)</math> and <math>\{y\} + \{2y\} + \{3y\} + \{4y\}\in [0, 4)</math>. This suggests that <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math> is in the interval <math>[0, 6)</math>. | + | Let <math>\lfloor x\rfloor = x - \{x\}</math>. Then, <math>\lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor</math> can be rewritten as <math>y - \{y\} + 2y - \{2y\} + 3y - \{3y\} + 4y - \{4y\}</math>, or <math>10y - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math>. Substituting <math>\lfloor y\rfloor + \{y\}</math> for <math>y</math> yields <math>10\lfloor y\rfloor + 10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math>. Since <math>10\lfloor y\rfloor</math> will always be a multiple of <math>10</math>, we must find the range of <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math>. Clearly, <math>10\{y\}\in \left[0, 10\right)</math> and <math>\{y\} + \{2y\} + \{3y\} + \{4y\}\in \left[0, 4\right)</math>. This suggests that <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math> is in the interval <math>\left[0, 6\right)</math>. |
− | Next, we must prove that the expression hits every integer in that interval. To do this, we look at the intervals between places where the expression makes a discontinuous leap. This happens when one of the values <math>\{y\}</math>, <math>\{2y\}</math>, <math>\{3y\}</math>, or <math>\{4y\}</math> resets to 0, which happens when <math>y</math>, <math>2y</math>, <math>3y</math>, or <math>4y</math> is an integer. This occurs when <math>y \in \{0, \dfrac14, \dfrac13, \dfrac12, \dfrac23, \dfrac34, 1\}</math>. In each of the intervals between these numbers, the expression is continuous. In the first interval, when <math>y \in [0, \dfrac14)</math>, <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math> ranges from <math>0</math> to <math>\dfrac52</math>. In the last interval, when <math>y \in [\dfrac34, 1)</math>, the expression ranges from <math>\dfrac32</math> to <math>4</math>. These two intervals combined hit all the numbers in <math>[0, 4)</math>. Thus, as <math>y</math> ranges from <math>0</math> to <math>1</math>, the expression <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math> hits all the numbers in the interval <math>[0, 6)</math>. | + | Next, we must prove that the expression hits every integer in that interval. To do this, we look at the intervals between places where the expression makes a discontinuous leap. This happens when one of the values <math>\{y\}</math>, <math>\{2y\}</math>, <math>\{3y\}</math>, or <math>\{4y\}</math> resets to 0, which happens when <math>y</math>, <math>2y</math>, <math>3y</math>, or <math>4y</math> is an integer. This occurs when <math>y \in \left\{0, \dfrac14, \dfrac13, \dfrac12, \dfrac23, \dfrac34, 1\right\}</math>. In each of the intervals between these numbers, the expression is continuous. In the first interval, when <math>y \in \left[0, \dfrac14\right)</math>, <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math> ranges from <math>0</math> to <math>\dfrac52</math>. In the last interval, when <math>y \in \left[\dfrac34, 1\right)</math>, the expression ranges from <math>\dfrac32</math> to <math>4</math>. These two intervals combined hit all the numbers in <math>[0, 4)</math>. Thus, as <math>y</math> ranges from <math>0</math> to <math>1</math>, the expression <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math> hits all the numbers in the interval <math>[0, 6)</math>. |
Finally, to find the answer, we know all numbers that are less than 6 greater than a multiple of <math>10</math> can be expressed, so the answer is <math>\boxed{600}</math> (any number ending in <math>0</math>, <math>1</math>, <math>2</math>, <math>3</math>, <math>4</math>, or <math>5</math>). | Finally, to find the answer, we know all numbers that are less than 6 greater than a multiple of <math>10</math> can be expressed, so the answer is <math>\boxed{600}</math> (any number ending in <math>0</math>, <math>1</math>, <math>2</math>, <math>3</math>, <math>4</math>, or <math>5</math>). |
Revision as of 04:54, 25 July 2020
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
We will be able to reach the same number of integers while ranges from 0 to 1 as we will when
ranges from
to
for any integer
(Quick proof:
). Since
, the answer must be exactly 50 times the number of integers we will be able to reach as
ranges from 0 to 1, including 1 but excluding 0.
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 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
Imagine that we increase from
to
. At the beginning, the value of our expression is
, at the end it is
. How many integers between
and
did we skip? We skip some integers precisely at those points where at least two of
,
,
, and
become integers at the same time.
Obviously, for and
all four values become integers at the same time, hence we skip three integers at each of these locations. Additionally, for
and
the values
and
become integers at the same time, hence we skip one integer at each of the locations.
Therefore for we skip a total of
integers. As in Solution 2, we conclude that we hit
of the integers from
to
, and so we hit
of the first
.
Solution 5
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 6
First, let to simplify the question. The expression in the question then becomes
.
Let . Then,
can be rewritten as
, or
. Substituting
for
yields
. Since
will always be a multiple of
, we must find the range of
. Clearly,
and
. This suggests that
is in the interval
.
Next, we must prove that the expression hits every integer in that interval. To do this, we look at the intervals between places where the expression makes a discontinuous leap. This happens when one of the values ,
,
, or
resets to 0, which happens when
,
,
, or
is an integer. This occurs when
. In each of the intervals between these numbers, the expression is continuous. In the first interval, when
,
ranges from
to
. In the last interval, when
, the expression ranges from
to
. These two intervals combined hit all the numbers in
. Thus, as
ranges from
to
, the expression
hits all the numbers in the interval
.
Finally, to find the answer, we know all numbers that are less than 6 greater than a multiple of can be expressed, so the answer is
(any number ending in
,
,
,
,
, or
).
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 |