19
$\begingroup$

Suppose that there are $10$ people at a party whose (integer) ages range from $0$ to $100$.

Show that there are two distinct, but not necessarily disjoint, subset of people that have exactly the same total age.

So my thoughts so far are that you could split the ages $0-100$ $(101$ numbers$)$ into $11$ groups (pigeons) and then categorize these groups into the $10$ people (holes). However this seems backwards and not sound to me. Is there a different way to think about this problem?

Any help is appreciated.

$\endgroup$
3
  • 2
    $\begingroup$ Similar earlier question (but with a different age limit): math.stackexchange.com/questions/320555/… $\endgroup$ Feb 28, 2018 at 23:58
  • $\begingroup$ Thank you. And thank you all for your help in understanding this problem. $\endgroup$
    – C.Math
    Mar 1, 2018 at 0:35
  • 8
    $\begingroup$ The “not necessarily disjoint” is not needed in the question (i.e. the claim is true even without that allowance): if two sets are not disjoint, we can remove the people common to both, from each. (Of course, it's possible that we'll end up with one empty set and another with people of ages 0, if one of the two original sets was a subset of the other.) $\endgroup$ Mar 1, 2018 at 1:21

4 Answers 4

34
$\begingroup$

The sum of ages cannot exceed $100 \times 10=1000$ $(1001$ cages, including $0 )$. The total ways to chose subsets of people are $2^{10}=1024$ $(1024$ pigeons$)$.

Can you see that coming?

$\endgroup$
15
$\begingroup$

Hint: how many subsets are there? What is the maximum total age of a subset?

$\endgroup$
6
$\begingroup$

To expand on what Ross said, your holes will be the total age of the group. How many holes are there? This is equivalent to asking what the minimal and maximal possible total ages are. Your pigeons will be the groups (this is the number of subsets).

When you find these two numbers, if the number of pigeons is larger than the number of buckets, you know you have two groups (not necessarily disjoint) with the same total age.

$\endgroup$
1
$\begingroup$

Adapting the analysis from this answer

If two people are the same age we are done, so assume everyone is a different age.

The number of non-empty subsets will be $2^{10}-1=1023$. We can immediately see this is greater than the maximum feasible age sum $\sum_{91}^{100}i = 955$ so there must be some duplicate sums.

Clearly there is room to raise the age limit. This analysis allows us to get to $\color{red}{106}$ since $\sum_{97}^{106}i = 1015<1023$ but we can do better.


Consider the youngest person, with an age of $y$ - this is the lower limit of possible age sums. The upper limit with the orginal age limit is then at most $y+\sum_{92}^{100}i = y+864$. There are thus $864$ or fewer different age sums available for different groups and we can extend the limit by $\lfloor({1023-864})/({9})\rfloor = 17$ years to $\color{red}{117}$.

We're not done...

With distinct ages, the full set sum is clearly not going to match any other subset, and neither is any subset with only one missing person unless that person is the oldest. So in a group of $n$ people we can discard $n$ subsets and reduce the highest possible total by the age limit. So for $10$ people, considering the $1013$ groups defined under this process we can impose an age limit of $\color{red}{130}$ since the feasible totals range of our chosen subsets is $y$ to $y+\sum_{122}^{129}i = y+251\cdot 4 = y+1004$ for $1005$ possible totals, allowing the pigeonhole argument again.


Finally note that this age limit is likely an underestimate of the maximum possible. Leaving only one "young end" age can produce huge gaps in the possible age sums (fewer holes for our pigeons). So it is almost certain that the highest possible age limit is still higher.

$\endgroup$
3
  • $\begingroup$ Same as Jaideep's idea. $\endgroup$ Mar 12, 2018 at 15:46
  • $\begingroup$ @richard1941 I suggest you need to read more than a few words of an answer to make any such assessment. If that's your downvote, you have no good reason for giving it. $\endgroup$
    – Joffan
    Mar 12, 2018 at 17:44
  • $\begingroup$ sorry. comment in haste, repent in liesure. :-( $\endgroup$ Mar 21, 2018 at 17:51

You must log in to answer this question.

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