Prove the geometric "Pigeonhole Principle"

393 Views Asked by At

This question is part of an introductory combinatorics class, so I don't know what measure theory is, but the question was stated as follows:

Suppose $A_1, A_2,... A_k, B$ are sets which contain a 'measure' such as length or area. Suppose that for every i, $A_i \subseteq B$. We will refer to the 'size' of $A$ according to the measure as $|A|$. Suppose that $\sum_{i=1}^{k} |A_i| > n|B|$. Then there are n+1 sets $A_{i_1},...,A_{i_{n+1}}$ such that their intersection isn't empty.

I managed to prove for the case n = 1, but haven't managed anything else. Any ideas?

1

There are 1 best solutions below

0
On

Suppose there are not $n+1$ such sets. Then for any point $x \in B$, $x$ is contained in at most $n$ of the $A_i$'s. Now if we measure all of the $A_i$'s, each point $x \in B$ gets "counted" at most $n$ times, in other words, $\sum_{k=1}^n |A_i| \leq n|B|$. Contradiction.

To make this more rigorous you really need a little measure theory. Define $f(x)=\sum_{i=1}^k 1\{x\in A_i\}$, where $$1\{x \in A_i\} = \begin{cases}1 & x \in A_i \\ 0 & x \notin A_i\end{cases}.$$ Then $f(x)$ counts the number of $A_i$'s that $x$ is in, so $0 \leq f(x) \leq n$ for all $x \in B$. So, $$\sum_{i=1}^k |A_i| = \sum_{i=1}^k \int_{x \in B} 1\{x \in A_i\} = \int_{x \in B}\sum_{i=1}^k1\{x \in A_i\} =\int_{x \in B}f(x) \leq \int_{x \in B} n = n|B|$$ where all of these integrals are with respect to the measure $|\cdot|$.