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$.

Question

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.

Answer 1

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.

Answer 2

• Assume that any couple of numbers are substitued by its difference to its symmetrical as follows $\{1,2,...n/2,n/2+1,...,n\}$=$\{n-1,(n-2)-2...,(n/2-n/2),1,...,n-1\}$

That means the set becomes; $\{5,3,1,1,3,5\}$

The probability of picking up any number is $1/6$

The probability of picking up any number added up to the previous not giving 7 is the probability of not chosing the same number again, that means $1/6*1/4$

The probabilty of picking up a third number not equals to both picked up ones is $1/6*1/4*1/2$ until this moment nothing left in the set to be picked up satisfying the condition so picking a forth number is of probabilty $1/6*1/4*1/2*0=0$

---

• Whether you want a generalization of your case, I thnk it fits to write down a rule concerning all sets of $n$ elements ${1,2,...,n}$ where:

Any combination of $n/2+1$ elements sub-set must give forcibly atleast one couple of sum=$n+1$

Answer 3

We can divide this set of number into three subset.

1. Chosen

2. Not to be chosen

3. Rest

If you keep add values in set-1,you can observe that set-2 is also increases. Eventually, set-1 and set-2 become equal and set-3 become empty. And if you want to add one value then there is no option other than set-2 since set-3 is empty (pigeonhole principle).