# Pigeonhole Question

This is an example from a Discrete math textbook: Any subset of size $6$ from the set $S = \{1,2, 4, \dots 9\}$ must contain two elements whose sum is $10$.

Answer: Here the pigeons constitute a $6$ elements subset of $\{1, 2, \dots 9\}$ and the pigeonholes are the subsets $\{1,9\}$, $\{2, 8\}$, $\{3,7\}$, $\{4,6\}$, $\{5\}$. The $6$ pigeons go to the their respective pigeonholes, they must fill at least one of the $2$ element subsets whose members sum to $10$.

There are ${9\choose 6}=84$ subsets. A lot of these don't add up to $10$; e.g,. $(1,2)$ and $(1,3)$ The subsets are the pigeonholes, thus the pigeonhole principle doesn't work. I understand that IF we restrict ourselves to the subsets, then the pigeonhole principle works. However, we are told to pick an arbitrary subset of size $6$ and that we are guaranteed that it will have $2$ elements that sum to $10$. This seems patently false.

Where am I going wrong?

The pigeonholes are the $5$ sets $\{1,9\},\{2,8\},\{3,7\},\{4,6\},\{5\}$. The pigeons are the $6$ numbers. Each of those $6$ pigeons is in one of the $5$ pigeonholes. Since there are $6$ pigeons and only $5$ pigeonholes, two pigeons must go into the same hole. Either two of your six numbers are in the set $\{1,9\}$, or two of them are in the set $\{2,8\}$, or two of them are in the set $\{3,7\}$, or two of them are in the set $\{4,6\}$. (The last pigeonhole doesn't have room for two pigeons.) There are four cases to check. I will do the first one. Suppose two of your pigeons are in the pigeonhole $\{1,9\}$. Then one of them is $1$ and the other is $9$, and so they add up to $10$ because $1+9=10$.
Consider the subsets {$1,9$}, {$2,8$}, {$3,7$}, {$4,6$}, and {$5$}. Select one integer from each subset. This gives use a set of size $5$. The very next integer you select to put in your set guarantees that there exists two integers in your set that sum to $10$. Thus any subset of size $6$ from the set $S=${$1,2,3,...,9$} must contain two integers whose sum is $10$.