[Math] Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$.

combinatorial-proofscombinatoricsdiscrete mathematicspigeonhole-principle

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$ using the Pigeonhole principle.

I am supposed to identify the pigeons and the pigeonholes.

We know that $\{1,6\},\{2,5\},$ and $\{3,4\}$ all add up to $7$, so I am guessing these are perhaps the pigeonholes?

We also know that any set of four numbers has six unique pairs in it. I am not really sure how to tie this to one of the pairs adding up to $7$, though.

Best Answer

If you are to avoid a pair adding to $7$ you can choose at most one member from each of the "pigeon-hole" sets $\{1,6\}, \{2,5\}, \{3,4\}.$ But then you can only choose at most $3$ numbers altogether..... $4$ pigeons (choices.)...$3$ holes.

Related Question