Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 AIME I Problems/Problem 13"
Line 11: Line 11:
 
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.
 
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>
 
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>
+
<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>
  
  

Revision as of 00:29, 17 September 2011

Problem

For each even positive integer $x$, let $g(x)$ denote the greatest power of 2 that divides $x.$ For example, $g(20)=4$ and $g(16)=16.$ For each positive integer $n,$ let $S_n=\sum_{k=1}^{2^{n-1}}g(2k).$ Find the greatest integer $n$ less than 1000 such that $S_n$ is a perfect square.


Solution

Given $g : x \mapsto \max_{j : 2^j | x} 2^j$, consider $S_n = g(2) + \cdots + g(2^n)$. Define $S = \{2, 4, \ldots, 2^n\}$. There are $2^0$ elements of $S$ that are divisible by $2^n$, $2^1 - 2^0 = 2^0$ elements of $S$ that are divisible by $2^{n-1}$ but not by $2^n, \ldots,$ and $2^{n-1}-2^{n-2} = 2^{n-2}$ elements of $S$ that are divisible by $2^1$ but not by $2^2$.

Thus $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)$, so we need $2^{2k} | n+1$ for $k \in \N$ (Error compiling LaTeX. Unknown error_msg). Now notice we also require $n < 1000$, so if $16 | n+1$ also (but $32 \not | \, n+1$), then $\frac{n+1}{16} \le 62$, so we have $n+1 = 16, 16 \cdot 3^2, 16 \cdot 5^2, 16 \cdot 7^2$. If $16 \not | \, n+1$, then $\frac{n+1}{4} \le 250$, so we have $n+1 = 4, 4 \cdot 3^2, \ldots, 4 \cdot 13^2, 4\cdot 3^2 \cdot 5^2$. Finally, $n+1$ could possibly be $64, 64 \cdot 3^2$ or 256. The maximum possible $n$ is thus $4\cdot 3^2 \cdot 5^2 - 1 = 899$.

Alternate Solution

First note that $g(k)=1$ if $k$ is odd and $2g(k/2)$ if $k$ is even. so $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).$ $2k-1$ must be odd so this reduces to $2\sum_{k=1}^{2^{n-2}}1+g(2k) = 2(2^{n-2}+\sum_{k=1}^{2^n-2}g(2k)).$ 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 $S_0=1$ 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 $S_n$ we can note that if $n-1$ is odd then $n+1$ must be exactly divisible by an odd power of $2$. However, this means $n+1$ is even but it cannot be. Thus $n-1$ is even and $n+1$ is a large even square. The largest even square $< 1001$ is $900$ so $n+1= 900 => n=899$


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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_AIME_I_Problems/Problem_13&oldid=42322"