# Combinatorics: sets and subsets (pigeonhole principle)

Show that every subset with 6 elements of {1,2,3,4, ..., 9} contains 2 elements with sum 10.

I solved this (solution below) but I want to do this easier using the pigeonhole principle.

My attempt:

Claim: Every subset of {1,2,3, ..., 9} has either the following number combinations in it: (1,9),(2,8),(3,7),(4,6)

Proof:

Let A be the set with subsets with 6 elements of {1,2, ..., 9} that have (1,9) in it. Let B be the set with subsets with 6 elements of {1,2, ..., 9} that have (2,8) in it. Let C be the set with subsets with 6 elements of {1,2, ..., 9} that have (3,7) in it. Let D be the set with subsets with 6 elements of {1,2, ..., 9} that have (4,6) in it.

$|A \cup B \cup C \cup D| = |A| + |B| + |C| + |D| - |A \cap B| - |A \cap C| - |A \cap D| - |B \cap D| - |B \cap C| - |C \cap D| + |A \cap B \cap C| + |A \cap B \cap D| + |B \cap C \cap D| + |A \cap C \cap D| - |A \cap B \cap C \cap D| = 4\binom{7}{4} - 6\binom{5}{2} + 4\binom{3}{0} + 0 = 84$

But, the total amount of subsets with 6 elements is $\binom{9}{6} = 84$. We deduce that every subset has 2 elements with sum 10. QED.

Can someone give a hint on a good way to do this using the pigeonhole principle? This is supposed to be an exercise that has to be solved using PHP and I believe there is a way easier approach.

You have already identified that in the $\{1,2,..9\}$ set we have these four pairs that sum up to $10$: $(1,9), (2,8), (3,7), (4,6)$.
So taking $3$ numbers out of the $\{1,2,...9\}$ set we can "break" at most $3$ of the pairs. Thus we will have at least one pair out of these four remaining in our 6-element subset. QED.
Your proof, with a little rewording, is a good use of the pigeonhole principle. You have five pigeonholes, the four two element subsets you name and $\{5\}$. Your six pigeons are the selected numbers. Two must be in the same hole, so you must have both elements of one of the sets you name. These two will sum to $10$