# With the pigeon hole principle how do you tell which are the pigeons and which are the holes?

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?

• 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
• To flesh out a comment by user spd_25 posted as an answer. A more refined estimate for $S_A$ would allow the use of the pigeonhole principle here: The sum is minimum for the subset $\{\min S\}$, and bounded above by $\min S + 10 + 11 + 12 + 13 + 14$, i.e. $\min S \leq S_A \leq 60 + \min S$, which allows us to consider only 61 pigeonholes instead. See also math.stackexchange.com/q/2888844. (Maybe the textbook does go on to explain this after the quoted part.) – epimorphic Dec 2 '18 at 17:19

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.
When you are asked to show that "There are at least two $$X$$ with the same $$Y$$, then $$X$$ are usually the pigeons and $$Y$$ are usually the holes.