Putnam 2006, Problem B-2

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
$$\left| m + \sum_{s \in S} s \right| \leq \frac{1}{n+1}.$$

Solution:
Let $\{x\} = x - \lfloor x \rfloor$ denote the fractional part of $x$. For $i = 0, \ldots, n$, put $s_i = x_1 + \cdots + x_i$ (so that $s_0 = 0$). Sort the numbers $\{s_0\}, \ldots, \{s_n\}$ into ascending order, and call the result $t_0, \ldots, t_n$. Since $0 = t_0 \leq \cdots \leq t_n < 1$, the differences
$$t_1 - t_0, \ldots, t_n - t_{n-1}, 1 - t_n$$
are nonnegative and add up to 1. Hence (as in the pigeonhole principle) one of these differences is no more than $1/(n+1)$; if it is anything other than $1 - t_n$, it equals $\pm(\{s_i\} - \{s_j\})$ for some $0 \leq i < j \leq n$. Put $S = \{x_{i+1}, \ldots, x_j\}$ and $m = \lfloor s_i \rfloor - \lfloor s_j \rfloor$; then
$$\left|m + \sum_{s \in S} s\right| = |m + s_j - s_i|$$
$$= |\{s_j\} - \{s_i\}|$$
$$\leq \frac{1}{n+1},$$
as desired. In case $1 - t_n \leq 1/(n+1)$, we take $S = \{x_1, \ldots, x_n\}$ and $m = -\lceil s_n \rceil$, and again obtain the desired conclusion.