1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @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 $\endgroup$
    – Youssef13
    Jan 10, 2020 at 8:59
  • $\begingroup$ Sorry, I misread/misunderstood the question. $\endgroup$
    – Jaap Scherphuis
    Jan 10, 2020 at 9:07

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ It's not given that there are 2 sets with the same sum of ages. It's the required to proof. $\endgroup$
    – Youssef13
    Jan 10, 2020 at 9:02
  • 3
    $\begingroup$ 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). $\endgroup$
    – NL1992
    Jan 10, 2020 at 9:05
  • $\begingroup$ I believe you may have understood the question wrong. The possible 254 subsets are not guaranteed to be disjoints. $\endgroup$
    – Youssef13
    Jan 10, 2020 at 9:37
  • 4
    $\begingroup$ @Youssef13 They don't need to be disjoint, they just need to have the same sum. By removing their shared elements, you get two disjoint sets, and since you remove the same sum from both, the smaller disjoint sets will also have the same sum as each other. $\endgroup$
    – Vsotvep
    Jan 10, 2020 at 9:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .