Yay! Putnam! Part 2. Topic: Sets. Level: AIME/Olympiad.

Problem: (2006 Putnam - B2) Prove that, for every set $ X = \{x_1, x_2, \ldots, x_n\} $ of $ n $ real numbers, there exists a non-empty subset $ S $ of $ X $ and an integer $ m $ such that

$ \displaystyle \left|m+\sum_{s \in S} s\right| \le \frac{1}{n+1} $.

Solution: Essentially, it's telling us to find a subset such that the sum of the elements has fractional part $ \le \frac{1}{n+1} $ or $ \ge \frac{n}{n+1} $. Consider the partial sums of $ X $, i.e.

$ t_1 = x_1 $

$ t_2 = x_1+x_2 $

$ \cdots $

$ t_n = x_1+x_2+\cdots+x_n $.

Now partition the interval $ [0,1) $ into $ n+1 $ intervals of length $ \frac{1}{n+1} $, like so:

$ \left[0, \frac{1}{n+1}\right]; \left(\frac{1}{n+1}, \frac{2}{n+1}\right); \left[\frac{2}{n+1}, \frac{3}{n+1}\right); \cdots ;\left[\frac{n-1}{n+1}, \frac{n}{n+1}\right); \left[\frac{n}{n+1}, 1) $.

Let $ \{t_i\} $ denote the fractional part of $ t_i $. Clearly if $ \{t_i\} \in \left[0, \frac{1}{n+1}\right] $ or $ \{t_i\} \in \left[\frac{n}{n+1}, 1\right) $, the problem is solved because we simply choose $ t_i $ and the closest integer to it. If, on the other hand, none of the $ \{t_i\} $ fall into these sets, they must all be in the intervals

$ \left(\frac{1}{n+1}, \frac{2}{n+1}\right); \left[\frac{2}{n+1}, \frac{3}{n+1}\right); \cdots ;\left[\frac{n-1}{n+1}, \frac{n}{n+1}\right) $.

Since there are exactly $ n-1 $ of these and we have $ n $ $ \{t_i\} $'s, by the Pigeonhole Principle we know two such $ \{t_i\} $ fall into the same interval, say $ \{t_j\} $ and $ \{t_k\} $ with $ j < k $. Then we choose the set $ S = \{x_{j+1}, x_{j+2}, \ldots, x_k\} $. The sum of the elements is

$ \displaystyle x_{j+1}+x_{j+2}+\cdots+x_k = t_k-t_j $,

which satisfies

$ |\{t_k\}-\{t_j\}| \le \frac{1}{n+1} $.

This however, means that

$ \{t_k-t_j\} \le \frac{1}{n+1} $ or $ \{t_k-t_j\} \ge \frac{n}{n+1} $,

meaning that the set $ S = \{x_{j+1}, x_{j+2}, \ldots, x_k\} $ satisfies the desired property by choosing the appropriate $ m $, which is the closest integer to the sum. QED.

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

Comment: This was a pretty standard pre-olympiad level pigeonhole problem, though it had some interesting notation which I suspect threw some people off. Plus the fact that the property we are to prove is quite weak in that we only have to look at sets of consecutive elements. In any case, it was fun though a bit on the simple side.

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

Practice Problem: (2006 Putnam - B5) For each continuous function $ f: [0,1] \rightarrow \mathbb{R} $, let $ I(f) = \int_0^1 x^2f(x)dx $ and $ J(f) = \int_0^1 x[f(x)]^2dx $. Find the maximum value of $ I(f)-J(f) $ over all such functions $ f $.