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 A Problems/Problem 13"

(→‎Problem)
(→‎Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== 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 14:48, 25 September 2007

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$.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_AIME_A_Problems/Problem_13&oldid=16868"