- #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: