Sunday, January 28, 2007

Distasteful Distance. Topic: Sequences & Series. Level: AIME.

Problem: (1997 Putnam - B1) Let $ \{x\} $ denote the distance between the real number $ x $ and the nearest integer. For each positive integer $ n $, evaluate

$ \displaystyle F_n = \sum_{m=1}^{6n-1} \min(\{\frac{m}{6n}\}, \{\frac{m}{3n}\}) $.

Solution: Well since $ \frac{m}{6n} $ lies in the interval $ (0, 1) $, we can just characterize $ \min(\{x\}, \{2x\}) $ for all $ x \in (0, 1) $. We split it up into three intervals:

If $ 0 < x \le \frac{1}{3} $, we have $ \{x\} \le \{2x\} $ because $ 2x \ge x $ and $ 1-2x \ge x $.

If $ \frac{1}{3} < x \le \frac{2}{3} $, we have $ \{2x\} \le \{x\} $ because $ x \ge |1-2x| $ and $ 1-x \ge |1-2x| $.

If $ \frac{2}{3} < x < 1 $, we again have $ \{x\} \le \{2x\} $ because $ 2x-1 \ge 1-x $ and $ 2-2x \ge 1-x $.

This translates to $ 1 \le m \le 2n $, $ 2n+1 \le m \le 4n $, and $ 4n+1 \le m \le 6n-1 $, so we sum the intervals separately (note that we split the middle interval again into two parts to avoid absolute values):

$ \displaystyle \sum_{m=1}^{2n} \frac{m}{6n} = \frac{1}{6n} \cdot \frac{2n(2n+1)}{2} = \frac{2n+1}{6} $

$ \displaystyle \sum_{m=2n+1}^{3n} \left(1-\frac{m}{3n}\right) = \sum_{m=0}^{n-1} \frac{m}{3n} = \frac{1}{3n} \cdot \frac{(n-1)n}{2} = \frac{n-1}{6} $

$ \displaystyle \sum_{m=3n+1}^{4n} \left(\frac{m}{3n}-1\right) = \sum_{m=1}^n \frac{m}{3n} = \frac{1}{3n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{6} $

$ \displaystyle \sum_{m=4n+1}^{6n-1} \left(1-\frac{m}{6n}\right) = \sum_{m=1}^{2n-1} \frac{m}{6n} = \frac{1}{6n} \cdot \frac{(2n-1)2n}{2} = \frac{2n-1}{6} $.

Summing them together we have

$ F_n = \frac{2n+1}{6}+\frac{n-1}{6}+\frac{n+1}{6}+\frac{2n-1}{6} = n $.

QED.

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

Comment: A pretty neat, although contrived, summation to just get simply to $ n $. The key was splitting the summation up; without doing that, it's really not possible to evaluate the sum in easy ways (like summing the first $ k $ positive integers multiple times). Figuring out how the function $ \{x\} $ worked helped a lot in determining the behavior of $ \min(\{x}, \{2x\}) $.

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

Practice Problem: Evaluate the sum

$ \displaystyle \sum_{i=1}^{\infty} \lfloor \frac{n+2^{i-1}}{2^i} \rfloor = \lfloor \frac{n+1}{2} \rfloor+\lfloor \frac{n+2}{4} \rfloor+\lfloor \frac{n+4}{8} \rfloor+\cdots $.

4 comments:

  1. I wouldn't be surprised if the summation you posted telescoped. Consider that min({ k/6n}, {k/3n}) is definitely related to min({(6n-k)/6n}, {(6n-k)/3n}).

    ReplyDelete
  2. I think they're equal. So you would just sum the first half... not that big of a difference o_O.

    ReplyDelete
  3. Anyway, the problem you posted is n by induction. You prove that only one of the expressions changes when n increments by 1.

    ReplyDelete