Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a room there are 10 people, none of whom are older than 60, but each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common person) the sum of whose ages is the same.

My approach: There are 1024 subsets, 1023 proper subsets. Therefore there are 1023 sums of ages and each sum is between 1 and 600. Then there are 600 places, but 1023 sums. Therefore at least two of them must be equal i.e. there exists different subsets $\{P_{i1}, \ldots, P_{in}\}$ and $\{P_{j1}, \ldots, P_{jn}\}$ such that the sum of the ages agree. Now take out the people present in both subsets.

Can 10 people be replaced by a smaller number?

I guess, it cannot. For example if there were to be $9$ people, then I would have $2^9-1 = 511$ proper subsets and since I have $600$ places, it is not guaranteed that there exists two disjoint groups of people such that the sum of whose ages are the same.

Am I right?

share|improve this question
2  
@MichaelBiro I would take out the same people as I stated in my approach? –  Xentius Mar 4 '13 at 16:39
1  
Your first argument looks right, but for the second part, you really ought to try demonstrating a counterexample. –  Ilmari Karonen Mar 4 '13 at 16:43
1  
@IlmariKaronen How can I do that? I chose the greatest number less than 10 and it does not satisfy what I need. So, what else I need to do? –  Xentius Mar 4 '13 at 16:47
1  
@Xentius: A counterexample would be a concrete set of 9 numbers $\le 60$ such that no two different subset have the same sum. It is not clear to me that one exists. –  Henning Makholm Mar 4 '13 at 16:50
    
@Xentius : Your TeX code does complicated things where simple things get better results. I changed {$P_i$$_1$, ..., $P_i$$_n$} to $\{P_{i1},\ldots,P_{in}\}$, coded as \{P_{i1},\ldots,P_{in}\}. –  Michael Hardy Mar 4 '13 at 17:42

3 Answers 3

As Ross and others have noted, your argument for 10 people is fine. To show that it's not possible to find two such groups out of 9 or fewer people, you should either exhibit a 9-person set that does not have two such subsets, or at least somehow prove that such a 9-person set exists.

Unfortunately, according to a brute force computer search I ran, such a counterexample does not seem to exist: there is no way to assign numbers between 1 and 60 to 9 people such that there would not be two subsets with the same sum. In fact, there doesn't seem to any 8-person counterexample either.

7-person counterexamples are easy to find, though: $(1, 2, 4, 24, 40, 48, 56)$ and $(60, 59, 58, 56, 53, 47, 36)$ are two of them. So now the interesting question becomes, is there some way to prove that an 8-person counterexample cannot exist without an exhaustive search?

share|improve this answer

Here is a (non-exhaustive) proof that a 9-person set doesn't exist. It looks at a more restrictive set, to greatly reduce the number of pigeonholes.

Let the ages of the people be (WLOG) $1 < a_1 < a_2 < \ldots a_9 \leq 60$. They have to be distinct, otherwise we are done.

Consider all subsets with at least 1 people. There are $2^9 - 1 = 511$ such sets. These are our pigeons, previously 512. The difference between the biggest and the smallest sum of ages is $a_2 + a_3 + \ldots a_9 \leq 452$. As such, the sum of ages can take on at most 453 different values. These are our pigeonholes, previously 540. Hence, by the Pigeonhole principle, there are 2 sets with the same sum. Now take the set difference, to ensure that we get 2 groups with no common people.

This approach does not extend to showing that a 8-person set doesn't exist, as claimed by Ilmari.

share|improve this answer
    
I'm not sure I follow you. The largest possible sum for a subset of at least $1$ is the subset of size $9$ where they are all $60$, which sums to $540$. The smallest possible sum for a subset of at least $1$ is the subset of one $1$-year old. The difference is $539 > 511$ What have I misunderstood? –  Avraham Sep 13 '13 at 0:49
1  
@Avraham The reason for that, is because you are holding 2 contradictory assumptions. In order to get a sum of 1, you need someone to have an age of 1. In order to get a sum of 540, you need everyone to have an age of 60. If you know that one person has an age of 1, what is the maximum sum of ages? (That's where $8\times 60$ comes from) I simply accounted for this. –  Calvin Lin Sep 13 '13 at 0:54
    
That makes eminent sense; thank you for explaining. –  Avraham Sep 13 '13 at 1:01

For the $10$ part you are fine. For the $9$ part, you haven't proven that it can be done, just that this approach isn't sufficient to rule it out. One way to finish the $9$ part is to display a set of $9$ numbers that you can't find such a set of subsets. After a bit of searching I haven't found one.

share|improve this answer
    
According to what you say, I need to list all the subsets and only after that I can say that, such a subset does not exist. (Showing only two subsets and saying that we cannot have such two subsets is not enough I guess.) So, is not this method too long? –  Xentius Mar 4 '13 at 18:01
2  
No, you might be able to find a clever argument to prove that no such subset of $\{1,2,3\ldots,60\}$ exists. As there are about $14$ billion subsets, you can't reasonably try them all. The sort of cleverness (this doesn't work): suppose $1$ is in the set. Then you can't have any neighboring numbers and might as well assume all the rest are even. Now you need to pick $8$ out of the evens, and you are really solving the problem of picking $8$ out of $30$ (divide the ones picked by $2$). The max sum is then 240 and there aren't 2^8=256 possible sums. –  Ross Millikan Mar 4 '13 at 18:15
    
@RossMillikan I found a clever argument for 9 :) –  Calvin Lin Sep 13 '13 at 0:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.