# Help with understanding Pigeonhole Principle concepts

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:

1. 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?

1. 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?

• If you have $k$ subsets, each with $(r-1)$ elements, then adding 1 more element to any of the subsets must produce a subset with $r$ elements. So, you want the minimum positive integer $N$ such that $N > (k)(r-1).$ In general, if $a$ is a positive integer, the minimum integer $N$ such that $N > a$ will be $N = a+1$. For example, the minimum integer $> 5$ is $6$. Oct 5, 2021 at 14:09
• 1) If $a, b$ are both integers and $a > b$, do you see why $a \geq b+1$? If you didn't get that, a simpler version is: If $a$ is an integer such that $a > 5$, what is the minimum value of $a$? 2) $|S_i|$ is the size of the subset $S_i$. That's common notation (which might be defined in the introduction of the book). Oct 5, 2021 at 14:09

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.$$

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.$$
$$\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$$.