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

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.