Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For example, I was reading this example from my textbook:

Let S be a set of six positive integers who maximum is at most 14. Show that the sums of the elements in all the nonempty subsets of S cannot all be distinct.

For each nonempty subset A of S the sum of the elements in A denoted $$S_A$$ satisfies $$1\leq S_A \leq 9+10+...+14=69$$ and there are $$2^6-1=63$$ nonempty subsets of S. We should like to draw the conclusion from the pigeonhole principle by letting the possible sums, from 1 to 69 be the pigeonholes with 63 nonempty subsets of S as the pigeons but then we have too few pigeons.

Why can't you say that there are 63 pigeonholes and 69 pigeons?

share|improve this question
    
I'm reminded of a sicker statement of the piegonhole principle: if you have $n$ pigeons and put $k$ holes in them, where $k > n$, then at least one pigeon will have at least two holes in it. –  Nate Eldredge Oct 31 '13 at 3:15

1 Answer 1

up vote 0 down vote accepted

In this example you are putting the subsets of $S$ (which all have sums) and placing them into the sums of $1$ to $69$. Think of the sums of $S$ as bins, we only have $63$ non empty subsets, and $69$ bins to put them in.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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