1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$
  • 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$

$\endgroup$
  • $\begingroup$ In set theory there are useful applications of the Transfinite Pigeonhole Principle.One example is that if uncountably many pigeons fly into countably many pigeon- holes, at least one hole has uncountably many pigeons. $\endgroup$ – DanielWainfleet Nov 7 '15 at 12:44
  • $\begingroup$ @user254665 i missed pigeon-holes definition, but i have no doubts that is not different than my approach $\endgroup$ – Abr001am Nov 7 '15 at 13:44
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.