Difference between revisions of "2006 AIME I Problems/Problem 13"
m (rv) |
Coppero1237 (talk | contribs) |
||
Line 7: | Line 7: | ||
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>. | 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>. | ||
+ | |||
+ | == Alternate Solution == | ||
+ | First note that <math>g(k)=1</math> if <math>k</math> is odd and <math>2g(k/2)</math> if <math>k</math> is even. | ||
+ | so <math> S_n=\sum_{k=1}^{2^{n-1}}g(2k). = \sum_{k=1}^{2^{n-1}}2*g(k) = 2\sum_{k=1}^{2^{n-1}}g(k) = 2\sum_{k=1}^{2^{n-2}} g(2k-1)+g(2k).</math> | ||
+ | <math>2k-1</math> must be odd so this reduces to <math>2\sum_{k=1}^{2^{n-2}}1+g(2k) = 2(2^{n-2}+\sum_{k=1}^{2^n-2}g(2k).</math> Thus <math>S_n=2\cdot(2^{n-2}+S_n-1)=2^{n-1}+2\cdotS_n-1.</math> Further noting that <math>S_0=1</math> we can see that <math>S_n=2^{n-1}\cdot(n-1)+2^n\cdotS_0=2^{n-1}\cdot(n-1)+2^{n-1}\cdot2=2^{n-1}\cdot(n+1). </math> which is the same as above. To simply the process of finding the largest square <math>S_n</math> we can note that if <math>n-1</math> is odd then <math>n+1</math> must be exactly divisible by an odd power of <math>2</math>. However, this means <math>n+1</math> is even but it cannot be. Thus <math>n-1</math> is even and <math>n+1</math> is a large even square. The largest even square <math>< 1001</math> is <math>900</math> so <math>n+1= 900 => n=899</math> | ||
+ | |||
== See also == | == See also == |
Revision as of 16:23, 7 February 2010
Contents
[hide]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 .
Alternate Solution
First note that if is odd and if is even. so must be odd so this reduces to Thus $S_n=2\cdot(2^{n-2}+S_n-1)=2^{n-1}+2\cdotS_n-1.$ (Error compiling LaTeX. Unknown error_msg) Further noting that we can see that $S_n=2^{n-1}\cdot(n-1)+2^n\cdotS_0=2^{n-1}\cdot(n-1)+2^{n-1}\cdot2=2^{n-1}\cdot(n+1).$ (Error compiling LaTeX. Unknown error_msg) which is the same as above. To simply the process of finding the largest square we can note that if is odd then must be exactly divisible by an odd power of . However, this means is even but it cannot be. Thus is even and is a large even square. The largest even square is so
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 |