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