3
$\begingroup$

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?

$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Where you are going wrong, is that you are trying to answer a question that wasn't asked, or adding things that have no relevance. The fact, that there are 2 element subsets of the 9 numbers, that don't have the sum to 10 property, is irrelevant, unless you can prove they all don't. The number of subsets of 6, also doesn't matter, we are seeking a general case, that works for all. A single set, with these properties failing, is all it would take to make a counterexample. But the proof, is as simple as showing any set of 6 numbers, must contain both elements from at least one of the two element sets, mentioned in the answer. If you can find a distinct set of 6 of the numbers, that doesn't force that to happen. you can disprove it. As there are only 5 sets, and 6 items, at least 2, must be from one of the sets. All of the two element sets given, sum to 10. Therefore the conclusion, that the two element subset, of the 6 exist, proves what was needed to be proven via the pigeonhole principle.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .