# Putnam PigeonHole

This is from page 12 of Putnam and Beyond.

Problem:

Prove that for every set $X ={x_1,x_2, \ldots ,x_n}$ of $n$ real numbers, there exists a nonempty subset $S$ of $X$ and an integer $m$ such that

$$\left| m + \sum\limits_{s\in S} s\right| \leq \frac{1}{n+1}$$

Solution:

Recall that the fractional part of a real number x is $x − \lfloor{x} \rfloor$ Let us look at the fractional parts of the numbers $x_1, x_1 + x_2, \ldots,x_1 + x_2 +\cdots+x_n$. If any of them is either in the interval $[0, \frac{1}{n+1}]$ or $[\frac{n}{n+1}, 1]$, then we are done. If not, we consider these n numbers as the “pigeons’’ and the $n − 1$ intervals $[\frac{1}{n+1}, \frac{2}{n+1}]$, $[\frac{2}{n+1}, \frac{3}{n+1}],\ldots, [\frac{n-1}{n+1}, \frac{n}{n+1}]$ as the “holes.’’ By the pigeonhole principle, two of these sums, say $x_1 +x_2 +\cdots+x_k$ and $x_1+x_2+\cdots+x_k+m$, belong to the same interval. But then their difference $x_k+1+\cdots+x_k+m$ lies within a distance of $\frac{1}{n+1}$ of an integer, and we are done.

My Question:

I am pretty lost in this question and I can't really see how the solution connects with the problem. I would appreciate it if someone could simplify/break it down for me.

• There are negative reals, and even negative integers. – André Nicolas May 25 '12 at 18:55
• But there is absolute sign? – Mat.S May 25 '12 at 18:58
• Imagine $m=5$, $s_1=-2.5$, $s_2=-2.4$. Then absolute value of sum is $0.1$. – André Nicolas May 25 '12 at 19:02
• Ok, what is the motivation behind looking at fractional parts? – Mat.S May 25 '12 at 19:16
• You want a partial sum to be close to an integer. You look at the fractional parts because the integer parts are irrelevant to the problem. This enables you to narrow the possibilities down so that the pigeonhole principle works - the partial sums are constricted so that two of them have to be close to each other. – Mark Bennet May 25 '12 at 19:18

You have copied down the solution wrong, but the solution also has an error (namely notational conflict). Here is an alternate presentation of the same solution, which is more explicit and avoids the conflict:

Let $F(x)=x-\lfloor x \rfloor$ be the fractional part of $x$, as defined in your solution. Define $y_i=F(x_1+x_2+\cdots+x_i)$ for $i=1, \ldots, n$. Each $y_i$ is in $[0,1)$. We partition $[0,1)$ into $n+1$ subintervals $[0,\frac{1}{n+1}),[\frac{1}{n+1},\frac{2}{n+1}),\ldots,[\frac{n}{n+1},1)$.

The basic idea is showing that either one of the $y_i$ is close enough to 0 or 1 to give a solution, or else two of them are close enough that their difference gives a solution.

If any of the $y_i$ are in $[0,\frac{1}{n+1})$ then we have $x_1+\cdots+x_i = \lfloor x_1+\cdots+x_i \rfloor + y_i$. Set $m=-\lfloor x_1+\cdots+x_i \rfloor$ and $S=\{x_1, \ldots, x_i \}$. Then we have that the LHS of your inequality is just $|y_i|=y_i \le \frac{1}{n+1}$. Similarly if any of the $y_i$ are in $[\frac{n}{n+1},1)$ then set $m=-\lfloor x_1+\cdots+x_i \rfloor-1$ and $S=\{x_1, \ldots, x_i \}$. Then the LHS is $|y_i-1|=1-y_i \le \frac{1}{n+1}$.

If neither of the above happen, then you have two of the $y_i$ in the same interval. Say these are $y_k$ and $y_{k+r}$. (This is where the book makes a notational error. They use $m$, which is already used in the problem statement. I've used $r$ in place of $m$). Since the interval has length $\frac{1}{n+1}$, the distance between them is at most $\frac{1}{n+1}$. So $|y_{k+r}-y_k| \le \frac{1}{n+1}$.

Set $S= \{ x_{k+1} , \ldots , x_{k+r} \}$. There are two cases to consider. First, we consider the case $y_{k+r} \ge y_k$. In this case, we have $y_{k+r}-y_k = F(x_{k+1} + \cdots + x_{k+r})$. Setting $m=- \lfloor x_{k+1} + \cdots + x_{k+r} \rfloor$ will give a LHS of $y_{k+r}-y_k \le \frac{1}{n+1}$. In the other case, $y_{k+r} < y_k$, and $y_{k+r}-y_k = F(x_{k+1} + \cdots + x_{k+r})-1$. In this case set $m= 1 - \lfloor x_{k+1} + \cdots + x_{k+r} \rfloor$. You'll get the LHS to be $|y_{k+r}-y_k| \le \frac{1}{n+1}$, which completes the proof.

• Thanks for clarifying, it is a lot more clear. – Mat.S May 26 '12 at 3:01