A question related to Pigeonhole Principle

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?


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?


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.


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.