Let $ S = \{ z_1,...,z_{100} \} \subseteq \Bbb R $. By PHP show $\exists T\subseteq S$.$\exists m\in\Bbb Z$. $|\sum_{x\in T}x-m|\leq\frac{1}{100}$

40 Views Asked by At

Problem: Let $ S = \{ z_1,...,z_{100} \} \subseteq \Bbb R $ be a set of reals. Using pigeon-hole principle, Show there exists a subset $ T \subseteq S $ which satisfies that there exists $ m \in \Bbb Z $ for which $ | \sum_{x \in T} x -m | \leq \frac{1}{100} $.

Note: I'm not sure if the $ m $ above is part of the sum, my instructor said yes but I am still not entirely convinced.

I don't really know what to do to solve the problem, it doesn't seem like a problem solved by PHP. I don't see how the proof can be constructive as to the construction of $ T $, maybe I need to write it first explicitly based on $ S $ , then I think I should denote $ H_k = x_1 + ... + x_k $ so that $ | \sum_{x \in T} x -m | = | H_n -m | \leq \frac{1}{100} $ , where $ |T| = n $. Afterwards, I should look at the inequality $ m - \frac{1}{100} \leq H_n \leq m+ \frac{1}{100}$ and somehow create pigeon-holes which are the numbers that satisfy this inequality and the pigeons themselves will be the finite sequence $ H_1,H_2,...,H_n$.

I'd appreciate any kind of help as to how to solve the problem, I feel lost.

1

There are 1 best solutions below

1
On BEST ANSWER

There is a "cheating" solution that simply chooses $T=\emptyset, m=0$. Then the term $|\sum_{x \in T}x - m|$ becomes simply $0$. Let's assume $T\neq \emptyset$ from now on.

Let's also assume all the $z_i$ are different, so $|S|=100$, as otherwise you could be left with a $1$-element set $S=\{0.5\}$ where the proposition is incorrect, except for the cheating solution.

If you consider $m$ part of the sum, there are counterexamples where there is no solution (besides the cheating one). Set $z_k=0.5 + k*10^{-100}, k=1,\ldots,100$. If you choose some $T$ with at least one element, than for $m \le 0$ the terms in parenthesis below are all at least $0.5$, so

$$|\sum_{x \in T}(x - m)| = \sum_{x \in T}(x - m) \ge 0.5.$$

OTOH, if $m \ge 1$, then each term in parenthesis below is smaller than $-0.4$, so

$$|\sum_{x \in T}(x - m)| = -\sum_{x \in T}(x - m) > 0.4.$$

After this dissection of the problem statement, let's tackle the "real" question: You need to assume $|T|\ge 1$, $|S| = 100$ and that $m$ is not part of the sum.

Your definition of $H_k$ is actually a major step for the solution.

You now have $100$ sums $H_k, k=1,\ldots, 100$, and corresponding $100$ fractional parts $F_k$

$$F_k:=H_k - \lfloor H_k \rfloor, k=1,\ldots,100.$$

For those fractional parts, we have $0 \le F_k < 1, k=1,\ldots,100.$

Maybe now is a good time to stop reading and trying to continue on your own, using the $F_k$ in the pigeon hole principle.


Ok, so we can partition the interval $[0,1)$ into 100 intervals $[\frac{k-1}{100},\frac{k}{100}), k=1,\ldots,100$. If any of our $F_k$ already lies in $[0,\frac1{100})$, we are done, we simply choose $T=\{1,\ldots,k\},m=\lfloor H_k \rfloor$.

If not, we now have $100$ (not necessarily different) values $F_k$ that lie in $99$ intervals $[\frac{k-1}{100},\frac{k}{100}), k=2,\ldots,100$. So, by the pigeon hole principle, we have 2 different indices $k_1, k_2$ where the $F_{k_1}, F_{k_2}$ lie in the same interval. But that means the absolute value of their differnce can be at most the length of the interval:

$$|F_{k_1} - F_{k_2}| \le \frac1{100} \Longleftrightarrow |H_{k_1} - \lfloor H_{k_1} \rfloor - H_{k_2} + \lfloor H_{k_2} \rfloor| = |H_{k_1} - H_{k_2} - (\lfloor H_{k_1} \rfloor - \lfloor H_{k_2} \rfloor)|\le \frac1{100}.$$

But by the definition of the $H_k$, and assuming w.l.o.g. that $k_1 > k_2$, we get $H_{k_1} - H_{k_2} = z_{k_2+1}+\ldots+z_{k_1}$, so if we chose

$$T=\{k_2+1, k_2+2, \ldots, k_1\}, m=\lfloor H_{k_1} \rfloor - \lfloor H_{k_2} \rfloor,$$ then the above

$$|H_{k_1} - H_{k_2} - (\lfloor H_{k_1} \rfloor - \lfloor H_{k_2} \rfloor)| \le \frac1{100}$$

becomes exactly what we want to show exists:

$$|\sum_{x \in T}x - m| \le \frac1{100}$$

with $T,m$ chosen as stated above.


This is a general principle that can often be applied if there is an integer you can freely choose. Try to build these sums with $H_k$ as you did, and then the $F_k$ are in an interval of length $1$. So by the pigeon hole principle there need to be some that are "close together". Then you go back to the $H_{k}$'s and the $\lfloor H_{k} \rfloor$ parts somehow combine into the choosable integer.