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

Question

I encountered into the following problem from Wikipedia from "Pigeonhole principle" page.

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

Proof: The pigeonholes will be labelled by the two element subsets $\{1,9\}, \{2,8\}, \{3,7\}, \{4,6\}$ and the singleton $\{5\}$, five pigeonholes in all. When the six "pigeons" (elements of the size six subset) are placed into these pigeonholes, each pigeon going into the pigeonhole that has it contained in its label, at least one of the pigeonholes labelled with a two element subset will have two pigeons in it.

However I can not comprehend the last sentence of the proof. Suppose we have six element subset of set $S$, call it $\{x_1,x_2,x_3,x_4,x_5,x_6\}$. Since we have $5$ pigeonholes and $6$ pigeons (elements $x_i$) then some pigeonhole (suppose $\{1,9\}$) has at least two elements (suppose $x_1,x_2$). Why then $x_1+x_2=10$?

What if $\{x_1,x_2,x_3,x_4,x_5,x_6\}=\{1,2,4,6,8,9\}$ and for example two elements say $1,2$ are in pigeonhole $\{1,9\}$. But $1+2\neq 10$.

Can anyone explain my question in detail, please?

Answer 1

Each pigeon goes into the pigeonhole that matches its label. E.g. pigeon 3 goes into {3,7}. Since there are 5 pigeonholes and 6 pigeons, one of the holes with two labels must end up with 2 pigeons in it.

Does that help?

Answer 2

The meaning is the following. You divide your set $S$ into 5 parts (here called pigeonholes). Note that each part has exactly 2 numbers, and each part sums to 10. Hence, if you have 2 numbers from the same pigeonhole, they will sum to 10.

Now your subset of size 6, say $X$, has the numbers $x_1, \ldots, x_6$. By the pigeonhole principle, at least one pair of these must be from the same pigeonhole, hence they will sum to 10.

So for example if $X = \{1,2, \ldots, 6\}$ then $4$ and $6$ are from the same pigeonhole and must add to 10.

In your sample set $X = \{1,2,4,6,8,9\}$, there are 3 such pairs, but existence of only 1 is guaranteed always.

Answer 3

You are understanding the wrong thing

The principal states that "there exists a pair of solution" , not every pair is solution