I'm currently reading Discrete Mathematics - G. Chartrand & P. Zhang and I'm having trouble with understanding two concepts with the Pigeon Principle that are explained in the textbook:
- For given positive integers r and k, what is the minimum cardinality N of a set S such that if S is divided into k subsets, then at least one of these subsets has at least r elements? According to the Pigeonhole Principle, ⌈N/k⌉ = r. Since ⌈x⌉ < x + 1 for every real number x, it follows that $r = \lceil{\frac{N}{k}}\rceil < \frac{N}{k} + 1$, and so $\frac{N}{k} > r - 1$ or $N > k(r-1)$. Since $N$ and $k(r-1)$ are integers, this implies that $N \geq k(r-1) + 1$. Since N is the minimum integer with this property, $N = k(r−1)+1$.
How does the fact that $N$ and $k(r-1)$ are both integers imply that $N \geq k(r - 1) +1$? Where did the $+1$ even come from in this statement as well as the greater-than-or-equal inequality?
- The General Pigeonhole Principle A set S with n elements is partitioned into k pairwise disjoint subsets $S_1 , S_2 , ..., S_k$ , where $|S_i| ≥ n_i$ for a positive integer $n_i$ for $i = 1, 2,...,k$. Then each subset of S with at least $1 + \sum_{i=1}^{k}(n_i+1)$ elements contain at least $n_i$ elements of $S_i$ for some integer $i \leq i \leq k$.
What does $|S_i| \geq n_i$ mean? How can a subset (in a partition) of some set $S$ with $n$ elements be greater than $n$ total elements?
Part (2) is poorly written, with a typo.
Suppose that you have a set $S$ with $n$ elements.
Further suppose that $S$ is partitioned into $k$ pairwise disjoint subsets $S_1, S_2, \cdots, S_k$.
This means that none of the $k$ subsets intersect with any of the others and that $S = ( S_1 \cup S_2 \cup \cdots \cup S_k ).$
You are given that for $1 \leq i \leq k, |S_k| \geq n_i$.
This means that there are $k$ variables, $n_1, \cdots, n_k$ such that
$S_1$ has at least $n_1$ elements.
$S_2$ has at least $n_2$ elements.
$\cdots$
$S_k$ has at least $n_k$ elements.
As a consequence of this premise, you know that
$n \geq (n_1 + n_2 + \cdots + n_k).$
Suppose that a subset $T$ is constructed from set $S$.
Further suppose that for each subset $S_i$, you have that
$(S_i \cap T)$ has less than $n_i$ elements.
Then the most elements that subset $T$ can have is:
$(n_1 - 1)$ elements from $S_1$.
$(n_2 - 1)$ elements from $S_2$.
$\cdots$
$(n_k - 1)$ elements from $S_k$.
This means that the most elements that subset $T$ can have, without there being some subset $S_i$ such that $(S_i \cap T)$ has $n_i$ elements is
$$\left[\sum_{i=1}^k (n_i - 1)\right] ~=~ \left[\sum_{i=1}^k (n_i)\right] - k.$$
This means that if 1 more element is added to the subset $T$, then there will have to be some subset $S_i$ such that $(S_i \cap T)$ has at least $n_i$ elements.
So, the minimum number of elements in subset $T$ to guarantee that there is some subset $S_i$ such that $(S_i \cap T)$ has at least $n_i$ elements is
$$1 + \left[\sum_{i=1}^k (n_i)\right] - k.$$
Addendum
As an interesting variation of part (2), suppose that for each subset $S_i$, instead of the premise that $|S_i| \geq n_i$, you were given that $|S_i| = n_i.$
This would imply that
$\displaystyle n = n_1 + n_2 + \cdots n_k = \sum_{i=1}^k n_i$.
Then, the minimum number of elements that a subset $T$ could have, to guarantee that there is some subset $S_i$ such that $(S_i \cap T)$ has at least $n_i$ elements would be
$$1 + n - k.$$
This means that under the assumption that each subset $S_i$ has exactly $n_i$ elements, that any subset $T$ with at least $(1 + n - k)$ elements will have to completely contain some subset $S_i$. In other words, there would have to be some subset $S_i$ such that $S_i \subseteq T$.