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$
  • 2
    $\begingroup$ Similar earlier question (but with a different age limit): math.stackexchange.com/questions/320555/… $\endgroup$ – Ilmari Karonen Feb 28 '18 at 23:58
  • $\begingroup$ Thank you. And thank you all for your help in understanding this problem. $\endgroup$ – C.Math Mar 1 '18 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$ – ShreevatsaR Mar 1 '18 at 1:21
33
$\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$
  • $\begingroup$ Same as Jaideep's idea. $\endgroup$ – richard1941 Mar 12 '18 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 '18 at 17:44
  • $\begingroup$ sorry. comment in haste, repent in liesure. :-( $\endgroup$ – richard1941 Mar 21 '18 at 17:51

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.