Consider a set of 8 people all are at most 30 years old (age is given in full years). What is the minimum and maximum sum of ages for a non-empty subset? Using the pigeonhole principle, show that there are disjoint subsets with the same sum of ages.
Well, for the first part of the question, it's pretty easy. Minimum age happens if I got a subset with only 1 person, and s/he is one year old.
Maximum age happens if I got 8 persons, each is 30 years, so maximum is 240.
I couldn't solve second part of the question (pigeonhole).
Here is how I'm thinking:
First, I'm trying to find out how many possible sums are there (holes). At first, one can say there are 240 possible sums of the subsets (from 1 to 240).
But, Because I can't have non-empty subsets, then I can't choose all the 8 persons in one subset. Hence, possible sums are from 1 to 210.
So, the number of holes is 210 (Correct me if it's wrong).
I still can't find out the number of pigeons.
Best Answer
There are $2^8-2$ subsets of a set of 8 elements (besides the empty set and the whole set). By your analysis, there are 2 sets, $A$ and $B$, with the same sum of ages. If these are not disjoint, you can take $A-A\cap B$ and $B-A\cap B$. These are disjoint, non-empty, and have the same sum.