- #1
member 587159
Homework Statement
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 pidgeon hole principle.
Homework Equations
Pidgeon hole principle
Combinatorics
The Attempt at a Solution
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.
Can someone give a hint on a good way to do this using the pidgeon hole principle? This is supposed to be an exercise that has to be solved using PHP.
Last edited by a moderator: