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?
Best Answer
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?