3
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – Nate Eldredge Oct 31 '13 at 3:15
  • $\begingroup$ 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.) $\endgroup$ – epimorphic Dec 2 '18 at 17:19
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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