# Any subset of size $6$ from the set $S = \{1,2, 4, \dots 9\}$ must contain two elements whose sum is $10$.

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