# Number of disjoint non-empty subsets [pigeonhole]

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.

• @JaapScherphuis, If I choose 8 people in the first subset, and it's known that the two subsets are disjoints. Then, the second subset must be empty. That's why I said I can't choose a subset with all 8 people – Youssef13 Jan 10 '20 at 8:59
• Sorry, I misread/misunderstood the question. – Jaap Scherphuis Jan 10 '20 at 9:07

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.
• Note that $2^8-2=254$, which is greater than your number of possible sums (at most 240), so by pigeonhole you get these sets, using your own analysis (what you wrote in the question). – NL1992 Jan 10 '20 at 9:05