Question: I have simillar question like this one: [Pigeonhole Principle: 5 integers from 1 to 8, some pair has sum 9.](https://math.stackexchange.com/questions/91635/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: 
> 
> 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.
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.