Pigeonhole Principle: pick random integer from given set

Question

I have simillar question like this one: Pigeonhole Principle: 5 integers from 1 to 8, some pair has sum 9., but little different.

Let A = {1,2,3,4,5,6,7,8}. If five integers are selected from A, At least a pair of selected numbers will equal nine when added up.

The book explains the solution by dividing the number into 4 disjoint subsets and pointing out that if the numbers in each set are added together, they result in a sum of 9: {1,8},{2,7},{3,6},{4,5}.

The part I don't understand is why divide by four ? where did the number four come from?

Thanks for any help. Sorry if this question is almost same like the link that i given.

Answer 1

The book explains the solution by dividing the number into 4 disjoint subsets and pointing out that if the numbers in each set are added together, they result in a sum of 9: {1,8},{2,7},{3,6},{4,5}.

The part I don't understand is why divide by four ?

Alternative perspective:

Suppose that you have a set $S$ with exactly $(2k)$ elements, where $k$ is some positive integer. Further suppose that the set $S$ is partitioned into $k$ subsets, where each subset has $2$ elements. Here, the word partition signifies that:

• Each of the $k$ subsets is disjoint from all of the others.
• The union of the $k$ subsets is the set $S$.

Now suppose that you are required to select $(k+1)$ distinct elements from the set $S$. Is it the case that one of the $(k)$ subsets will have both of its elements selected?

Yes, because if you are constrained by only picking (at most) $1$ element from each of the $k$ subsets, then it will only be possible to select $k$ different elements. That is, when you then select the $(k+1)$-th element, it will have to come from one of the subsets from which you already selected an element.

This is (loosely) referred to as the pigeonhole principle. That is, if you have $(k+1)$ pigeons and $k$ pigeonholes, then $2$ of the pigeons have to be placed in the same pigeonhole.

You asked what is special about the number $(4)$ as it pertains to the posed problem. The problem specifically requires that $5 = (4+1)$ elements from $\{1,2,\cdots,8\}$ be selected.

This implies that if $\{1,2,\cdots,8\}$ can be partitioned into $(4)$ subsets of $2$ elements each, in a meaningful way, then it will be relevant that you were forced to select both elements from one of the $(4)$ subsets.

This is specifically because you are being required to select $(4+1)$ elements.

Then, the partitioning into
$\{1,8\}$
$\{2,7\}$
$\{3,6\}$
$\{4,5\}$

is specifically crafted so that when you select both elements from one of the $4$ subsets above, you will necessarily have selected some pair of elements that add up to $9$.

However, this all begs the question:
how was the problem originally crafted?

Answer:
It was recognized that the set $\{1,2,\cdots,8\}$ permitted the partitioning into the $4$ subsets shown above, such that in any of the $4$ subsets, the pair of numbers added up to $9$.

Then, once this was recognized, the problem composer realized that if you were forced to select $(4+1)$ different elements, then as discussed, you would be forced to select both elements from one of the $4$ subsets.

Answer 2

The four comes from the fact that there are exactly four distinct ways for two numbers from $A$ to add up to 9. This is how one applies the pigeon hole principle. You are selecting 5 (you probably need to assume they are distinct) numbers from $A$, each of which is a member of one of the four pairs. The pigeon hole principle implies that your selection will contain at least one of the pairs which add up to 9.