10 people,each of whom ages are $\ge1,\le60$. Show one can always find two groups of people (with no common person) the sum of whose ages is the same.

Question

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 $2^{10}=1024$ subsets, $1023$ non-empty subsets. Therefore there are $1023$ sums of ages and each sum is between $1$ and $600$. Then there are $600$ possible values, but $1023$ sums. Therefore at least two of them must be equal, i.e. there exist 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 now I have $9\cdot 60=540$ possible totals, 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?

Answer 1

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.

Answer 2

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?