Difference between revisions of "2007 AIME I Problems/Problem 7"
m (→Solution: syntax) |
m (→Solution) |
||
(11 intermediate revisions by 8 users not shown) | |||
Line 3: | Line 3: | ||
<math>N = \sum_{k = 1}^{1000} k ( \lceil \log_{\sqrt{2}} k \rceil - \lfloor \log_{\sqrt{2}} k \rfloor )</math> | <math>N = \sum_{k = 1}^{1000} k ( \lceil \log_{\sqrt{2}} k \rceil - \lfloor \log_{\sqrt{2}} k \rfloor )</math> | ||
− | Find the remainder when <math>N</math> is divided by 1000. (<math>\lfloor{k}\rfloor</math> is the greatest integer less than or equal to <math>k</math>, and <math>\lceil{k}\rceil</math> is the least integer greater than or equal to <math>k</math>.) | + | Find the [[remainder]] when <math>N</math> is divided by 1000. (<math>\lfloor{k}\rfloor</math> is the [[floor function|greatest integer]] less than or equal to <math>k</math>, and <math>\lceil{k}\rceil</math> is the [[ceiling function|least integer]] greater than or equal to <math>k</math>.) |
== Solution == | == Solution == | ||
− | The ceiling of a number minus the floor of a number is either equal to zero (if the number is an [[integer]]) | + | The ceiling of a number minus the floor of a number is either equal to zero (if the number is an [[integer]]); otherwise, it is equal to 1. Thus, we need to find when or not <math>\log_{\sqrt{2}} k</math> is an integer. |
− | The formula for the sum of an [[arithmetic | + | The change of base formula shows that <math>\frac{\log k}{\log \sqrt{2}} = \frac{2 \log k}{\log 2}</math>. For the <math>\log 2</math> term to cancel out, <math>k</math> is a [[exponent|power]] of <math>2</math>. Thus, <math>N</math> is equal to the sum of all the numbers from 1 to 1000, excluding all powers of 2 from <math>2^0 = 1</math> to <math>2^9 = 512</math>. |
+ | |||
+ | The formula for the sum of an [[arithmetic sequence]] and the sum of a [[geometric sequence]] yields that our answer is <math>\left[\frac{(1000 + 1)(1000)}{2} - (1 + 2 + 2^2 + \ldots + 2^9)\right] \mod{1000}</math>. | ||
+ | |||
+ | Simplifying, we get | ||
+ | <math>\left[1000\left(\frac{1000+1}{2}\right) -1023\right] \mod{1000} \equiv [500-23] \mod{1000} \equiv 477 \mod{1000}.</math> The answer is <math>\boxed{477}</math> | ||
== See also == | == See also == | ||
+ | *[[Logarithm]] | ||
{{AIME box|year=2007|n=I|num-b=6|num-a=8}} | {{AIME box|year=2007|n=I|num-b=6|num-a=8}} | ||
+ | |||
+ | [[Category:Intermediate Algebra Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 20:26, 20 April 2023
Problem
Let
Find the remainder when is divided by 1000. (
is the greatest integer less than or equal to
, and
is the least integer greater than or equal to
.)
Solution
The ceiling of a number minus the floor of a number is either equal to zero (if the number is an integer); otherwise, it is equal to 1. Thus, we need to find when or not is an integer.
The change of base formula shows that . For the
term to cancel out,
is a power of
. Thus,
is equal to the sum of all the numbers from 1 to 1000, excluding all powers of 2 from
to
.
The formula for the sum of an arithmetic sequence and the sum of a geometric sequence yields that our answer is .
Simplifying, we get
The answer is
See also
2007 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.