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

Question

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.

Answer 1

I am not sure if this would qualify for as a PHP approach, but this is the first thing I noticed:

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.

Answer 2

The naive approach (for PHP) would be to loop through every subset containing 6 elements and check the sum of every pair in each subset. If for every subset of 6 one of the pairs sum to 10, then the statement is true.

Answer 3

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$