0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ $x_1 + x_2$ is only one of the possible sums. $x_1 + x_6 = 10$ though which is the claim, not that all sums are $10$ but that there exists a pair that sum to $10$. $\endgroup$ – CyclotomicField Dec 19 '17 at 16:00
2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ That was the answer which I needed! Every pigeon (with some number) goes to the pigeonhole where one of the coordinates $\{x,y\}$ coincides with $m$, right? $\endgroup$ – ZFR Dec 19 '17 at 16:43
  • 1
    $\begingroup$ Yes, that is key. It is written very strangely to say the least... I was utterly confused at first reading. Best to have language being simple and direct in math! I'd be tempted to edit the wikipedia entry. Pigeon $m$ has no choice but to go into the pigeonhole ${x,y}$ where either $x=m$ or $y=m$ (with exception for $m=5$, but that doesn't affect anything since pigeon 5 sits all by itself). $\endgroup$ – jdods Dec 19 '17 at 18:36
  • $\begingroup$ Thanks a lot for clear answer! One of the reasons why I did not understand that text maybe that English is not my native language :) $\endgroup$ – ZFR Dec 19 '17 at 19:26
  • $\begingroup$ @RFZ, well, English is my native language and I was thoroughly confused, so don't feel bad! $\endgroup$ – jdods Dec 19 '17 at 21:33
1
$\begingroup$

You are understanding the wrong thing

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.