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

1.2k Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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.