Let $S=\{3,4,5,6,7,8,9,10,11,12\}$. Suppose 6 integers are chosen from S. Must there be 2 integers whose sum is 15?

Question

How can I go about solving this Pigeonhole Principle problem?

So I think the possible numbers would be: $[3+12], [4+11], [5+10], [6+9], [7+8]$

I am trying to put this in words...

Answer 1

Denote the set $[3,4,5,6,7,8,9,10,11,12]$ by $S$. This set has $10$ elements.

As you correctly noted, this set can be split into another set $T$ with $5$ elements, $[(3,12);(4,11);(5,10);(6,9);(7,8)]$, such that the binary sum of each of the components for each element is $15$.

If you pick $6$ integers from the set $S$, and wish that none of these picked numbers from this set $W$ can be grouped into a set of pairs with an element whose sum is $15$, then one must pick $6$ of the components from the set $T$ such that none of the components are part of the same element.

The Pigeon Hole Principle states that if $n$ items are put into $m$ containers, with $n \gt m$, then at least one container must contain more than one item. Let the number of integers needed to be fit equal $n$. Let the number of unique elements of $T$ be denoted by $m$. $$6 \gt 5$$ Therefore by the Pigeon Hole Principle, if one groups $W$ into arbitrary unique pairings, there will exist at least one grouping of $W$ into a set with pair whose sum is $15$.

Answer 2

If you pick five numbers from the set, you could pick exactly one from every pair you listed (and all numbers in the set are listed in exactly one pair). If you then pick another number then that must be from one of the five pairs you already have a number from. So you are guaranteed to end up with a pair that sums to fifteen from the pigeonhole principle.

Answer 3

The sentence you want is probably something along the lines of : "We need to pick $6$ distinct numbers from $5$ pairs of numbers. By the pigeonhole principle, both numbers in at least one of the pairs must be picked."

Answer 4

You can divide your set into three group

1. selected
2. Can't selected
3. total- {selected + can't selected}

As your selected set increase , you can observe that your second group is also increasing and both are equal. In the end , your total group become zero.

So , Next time when you want to select next element , you don't have any choice other than selection from group 2(Pigeonhole principle, Don't have choice to put all Ball in different Box , if we have n Box and n+1 Ball ).