1985 AIME Problems/Problem 10
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
?
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 1000.
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 |