0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Oct 5, 2021 at 14:09
  • $\begingroup$ 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). $\endgroup$
    – Calvin Lin
    Oct 5, 2021 at 14:09

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.