Difference between revisions of "2006 AIME I Problems/Problem 13"
(→Solution) |
m (rv) |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
+ | For each [[even integer | even]] [[positive integer]] <math> x </math>, let <math> g(x) </math> denote the greatest power of 2 that [[divisor | divides]] <math> x. </math> For example, <math> g(20)=4 </math> and <math> g(16)=16. </math> For each positive integer <math> n, </math> let <math> S_n=\sum_{k=1}^{2^{n-1}}g(2k). </math> Find the greatest integer <math> n </math> less than 1000 such that <math> S_n </math> is a [[perfect square]]. | ||
− | |||
== Solution == | == Solution == | ||
− | {{ | + | Given <math>g : x \mapsto \max_{j : 2^j | x} 2^j</math>, consider <math>S_n = g(2) + \cdots + g(2^n)</math>. Define <math>S = \{2, 4, \ldots, 2^n\}</math>. There are <math>2^0</math> elements of <math>S</math> that are divisible by <math>2^n</math>, <math>2^1 - 2^0 = 2^0</math> elements of <math>S</math> that are divisible by <math>2^{n-1}</math> but not by <math>2^n, \ldots,</math> and <math>2^{n-1}-2^{n-2} = 2^{n-2}</math> elements of <math>S</math> that are divisible by <math>2^1</math> but not by <math>2^2</math>. |
+ | |||
+ | Thus <math>S_n = 2^0\cdot2^n + 2^0\cdot2^{n-1} + 2^1\cdot2^{n-2} + \cdots + 2^{n-2}\cdot2^1 = 2^n + (n-1)2^{n-1} = 2^{n-1}(n+1)</math>, so we need <math>2^{2k} | n+1</math> for <math>k \in \N</math>. Now notice we also require <math>n < 1000</math>, so if <math>16 | n+1</math> also (but <math>32 \not | \, n+1</math>), then <math>\frac{n+1}{16} \le 62</math>, so we have <math>n+1 = 16, 16 \cdot 3^2, 16 \cdot 5^2, 16 \cdot 7^2</math>. If <math>16 \not | \, n+1</math>, then <math>\frac{n+1}{4} \le 250</math>, so we have <math>n+1 = 4, 4 \cdot 3^2, \ldots, 4 \cdot 13^2, 4\cdot 3^2 \cdot 5^2</math>. Finally, <math>n+1</math> could possibly be <math>64, 64 \cdot 3^2</math> or 256. The maximum possible <math>n</math> is thus <math>4\cdot 3^2 \cdot 5^2 - 1 = 899</math>. | ||
== See also == | == See also == |
Revision as of 18:35, 25 September 2007
Problem
For each even positive integer , let denote the greatest power of 2 that divides For example, and For each positive integer let Find the greatest integer less than 1000 such that is a perfect square.
Solution
Given , consider . Define . There are elements of that are divisible by , elements of that are divisible by but not by and elements of that are divisible by but not by .
Thus , so we need for $k \in \N$ (Error compiling LaTeX. Unknown error_msg). Now notice we also require , so if also (but ), then , so we have . If , then , so we have . Finally, could possibly be or 256. The maximum possible is thus .
See also
2006 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |