Sunday, November 5, 2006

Oh Really... Topic: S&S/Sets. Level: AIME/Olympiad.

Problem: (1999 IMC Day 1 - #2) Does there exist a bijective map $f(n): \mathbb{N} \rightarrow \mathbb{N}$ so that $\displaystyle \sum_{n=1}^{\infty} \frac{f(n)}{n^2}$ is finite?

Solution: Consider the bijective map $f_k(n): \{1,2, \ldots, k\} \rightarrow \{1,2, \ldots k\}$ and the sum $\displaystyle S_k = \sum_{n=1}^k \frac{f_k(n)}{n^2}$. Since the sets

$\{1, 2, \ldots, k \}$ and $\{\frac{1}{1^2}, \frac{1}{2^2}, \cdots, \frac{1}{k^2} \}$

are oppositely ordered, by Rearrangement we have

$\displaystyle S_k \ge \frac{1}{1^2}+\frac{2}{2^2}+\cdots+\frac{k}{k^2} = \sum_{n=1}^k \frac{1}{n}$.

Hence $\displaystyle \lim_{k \rightarrow \infty} S_k \ge \lim_{k \rightarrow \infty} \sum_{n=1}^k \frac{1}{n} = \infty$, so the answer is no. QED.

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

Comment: Basically, knowledge of the Rearragement inequality killed this problem. It's also useful to know what a bijective map is - a function $f:A \rightarrow B$ where $A$ and $B$ are sets such that for any $x, y \in A$ we have $f(x) = f(y) \Rightarrow x = y$ and for any $b \in B$ there exists $x \in A$ such that $f(x) = b$. A lot of higher level math is vocabulary and notation, which is sort of a pity, but that's just how it is.

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

Practice Problem: Evaluate $\displaystyle \int_0^{\infty} e^{-x^2}dx$.