Difference between revisions of "2006 AIME I Problems/Problem 13"
m (→Alternate Solution) |
Mathgeek2006 (talk | contribs) m (→Solution) |
||
Line 6: | Line 6: | ||
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>. | 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 < | + | Thus |
+ | <cmath>\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*}</cmath> Let <math>2^k</math> be the highest power of <math>2</math> that divides <math>n+1</math>. Thus by the above formula, the highest power of <math>2</math> that divides <math>S_n</math> is <math>2^{k+n-1}</math>. For <math>S_n</math> to be a perfect square, <math>k+n-1</math> must be even. If <math>k</math> is odd, then <math>n+1</math> is even, hence <math>k+n-1</math> is odd, and <math>S_n</math> cannot be a perfect square. Hence <math>k</math> must be even. In particular, as <math>n<1000</math>, we have five choices for <math>k</math>, namely <math>k=0,2,4,6,8</math>. | ||
+ | |||
+ | If <math>k=0</math>, then <math>n+1</math> is odd, so <math>k+n-1</math> is odd, hence the largest power of <math>2</math> dividing <math>S_n</math> has an odd exponent, so <math>S_n</math> is not a perfect square. | ||
+ | |||
+ | In the other cases, note that <math>k+n-1</math> is even, so the highest power of <math>2</math> dividing <math>S_n</math> will be a perfect square. In particular, <math>S_n</math> will be a perfect square if and only if <math>(n+1)/2^{k}</math> is an odd perfect square. | ||
+ | |||
+ | If <math>k=2</math>, then <math>n<1000</math> implies that <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>. | ||
+ | |||
+ | If <math>k=4</math>, then <math>n<1000</math> implies that <math>\frac{n+1}{16} \le 62</math>, so <math>n+1 = 16, 16 \cdot 3^2, 16 \cdot 5^2, 16 \cdot 7^2</math>. | ||
+ | |||
+ | If <math>k=6</math>, then <math>n<1000</math> implies that <math>\frac{n+1}{64}\le 15</math>, so <math>n+1=64,64\cdot 3^2</math>. | ||
+ | |||
+ | If <math>k=8</math>, then <math>n<1000</math> implies that <math>\frac{n+1}{256}\le 3</math>, so <math>n+1=256</math>. | ||
+ | |||
+ | Comparing the largest term in each case, we find that the maximum possible <math>n</math> such that <math>S_n</math> is a perfect square is<math>4\cdot 3^2 \cdot 5^2 - 1 = 899</math>. | ||
== Alternate Solution == | == Alternate Solution == |
Revision as of 17:23, 13 March 2015
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 Let be the highest power of that divides . Thus by the above formula, the highest power of that divides is . For to be a perfect square, must be even. If is odd, then is even, hence is odd, and cannot be a perfect square. Hence must be even. In particular, as , we have five choices for , namely .
If , then is odd, so is odd, hence the largest power of dividing has an odd exponent, so is not a perfect square.
In the other cases, note that is even, so the highest power of dividing will be a perfect square. In particular, will be a perfect square if and only if is an odd perfect square.
If , then implies that , so we have .
If , then implies that , so .
If , then implies that , so .
If , then implies that , so .
Comparing the largest term in each case, we find that the maximum possible such that is a perfect square is.
Alternate Solution
First note that if is odd and if is even. so must be odd so this reduces to Thus Further noting that we can see that which is the same as above. To simplify 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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.