Friday, December 23, 2005

Rounding Time! Topic: Number Theory. Level: AIME.

Problem: (1995 AIME - #13) Let $f(n)$ be the integer closest to $\sqrt[4]{n}$. Find

$\displaystyle \sum_{k=1}^{1995} \frac{1}{f(k)}$.

Solution: So how can we best define "integer closest?" It basically means

$ f(n) = x$ iff $ x-\frac{1}{2} < \sqrt[4]{n} < x+\frac{1}{2}$.

Note we may use strict bounds because we know $\sqrt[4]{n}$ will not have fractional part $\frac{1}{2}$.

So we can find bounds for $n$ such that $f(n) = x$.

We must have $ \left(x-\frac{1}{2}\right)^4 < n < \left(x+\frac{1}{2}\right)^4$.

Expanding, we get

$ x^4-2x^3+\frac{3}{2}x^2-\frac{1}{2}x+\frac{1}{16} < n < x^4+2x^3+\frac{3}{2}x^2+\frac{1}{2}x+\frac{1}{16}$

from which we get $4x^3+x$ integral solutions (subtract lower bound from upper).

Thus the summation can be divided into separate cases based on the value of $f(n) = x$. Since there are $4x^3+x$ terms and each has value $\frac{1}{x}$, they sum to $\frac{1}{x}(4x^3+x) = 4x^2+1$.

Since $7^4 > 1995$, we may only take this from $x = 1$ to $x = 6$, giving

$\displaystyle \sum_{i=1}^6(4i^2+1) = 4 \cdot \frac{(6)(6+1)(2 \cdot 6+1)}{6}+6 = 370$.

But this only accounts for

$\displaystyle \sum_{i=1}^6(4i^3+i) = 4\left(\frac{(6)(6+1)}{2}\right)^2+\frac{(6)(6+1)}{2} = 1785 $ terms.

So we have $1995-1785 = 210$ remaining terms, all of which are $ \frac{1}{7}$, giving the new total of $370+\frac{1}{7}(210) = 400$. QED.

--------------------

Comment: At this point, we're happy. Why? Because it's an AIME problem and we got an integer answer! And the chances of us doing it wrong and getting an integer answer is not too high, so we are probably right.

--------------------

Practice Problem: Find the smallest $m$ such that

$\displaystyle \sum_{k=1}^m \frac{1}{f(k)}$ exceeds $600$.

4 comments:

  1. 1. We want to take \sum 4k^2 + 1 until it becomes very close to 600, then keep adding terms until it exceeds 600. We want 4(n)(n+1)(2n+1)/6 + n > 600. To find an approximate answer, we will just write 4n^3/3 ~ 600, 4n^3 ~ 1800, n^3 ~ 450, which gives us either 7 or 8. 7 gets us 4(7)(8)(15)/6 + 7 = 567, which is as close to 600 as we can risk. This means we are using \sum 4k^3 + k = 4( 8(9)/2 )^2 + 8(9)/2 = 5220 terms.

    The terms after that are all going to have f(k) = 8, and we still have to make up for a sum of at least 23, so we need 8 * 23 = 184 more terms for a total of m = 5404 terms. I think.

    ReplyDelete
  2. Everything's right, except the sum of 4k^3+k from k=1 to 7 is actually

    4[(7*8)/2]^2+(7*8)/2 = 3164.

    So the answer should be 3164+184 = 3348.

    ReplyDelete
  3. 600-567=33 :P
    ...but shouldn't there be an extra term added so that the sum [i]exceeds[/i] 600?

    ReplyDelete