2006 AIME I Problems/Problem 13

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 $\begin{align*} 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).\end{align*}$ Let $2^k$ be the highest power of $2$ that divides $n+1$ . Thus by the above formula, the highest power of $2$ that divides $S_n$ is $2^{k+n-1}$ . For $S_n$ to be a perfect square, $k+n-1$ must be even. If $k$ is odd, then $n+1$ is even, hence $k+n-1$ is odd, and $S_n$ cannot be a perfect square. Hence $k$ must be even. In particular, as $n<1000$ , we have five choices for $k$ , namely $k=0,2,4,6,8$ .

If $k=0$ , then $n+1$ is odd, so $k+n-1$ is odd, hence the largest power of $2$ dividing $S_n$ has an odd exponent, so $S_n$ is not a perfect square.

In the other cases, note that $k+n-1$ is even, so the highest power of $2$ dividing $S_n$ will be a perfect square. In particular, $S_n$ will be a perfect square if and only if $(n+1)/2^{k}$ is an odd perfect square.

If $k=2$ , then $n<1000$ implies that $\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$ .

If $k=4$ , then $n<1000$ implies that $\frac{n+1}{16} \le 62$ , so $n+1 = 16, 16 \cdot 3^2, 16 \cdot 5^2, 16 \cdot 7^2$ .

If $k=6$ , then $n<1000$ implies that $\frac{n+1}{64}\le 15$ , so $n+1=64,64\cdot 3^2$ .

If $k=8$ , then $n<1000$ implies that $\frac{n+1}{256}\le 3$ , so $n+1=256$ .

Comparing the largest term in each case, we find that the maximum possible $n$ such that $S_n$ is a perfect square is $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}}2g(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(2^{n-2}+S_{n-1})=2^{n-1}+2S_{n-1}.$ Further noting that $S_0=1$ we can see that $S_n=2^{n-1}\cdot (n-1)+2^n\cdot S_0=2^{n-1}\cdot (n-1)+2^{n-1}\cdot2=2^{n-1}\cdot (n+1).$ which is the same as above. To simplify 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=$ \boxed{899}$

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

Page

Toolbox

Search

2006 AIME I Problems/Problem 13

Contents

Problem

Solution

Alternate Solution

See also