# 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?

• @MichaelBiro I would take out the same people as I stated in my approach? – Xentius Mar 4 '13 at 16:39
• 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
• @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
• @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. – hmakholm left over Monica Mar 4 '13 at 16:50
• There is no reason to disciminate against babies of $0$ years old. If any are present in the group then the singleton of this baby and the emtpy set will provide an example of two groups (and if not then we can forget about the empty set as before). In other words the result remains unchanged (and true) if we allow for an age of$~0$. – Marc van Leeuwen Feb 14 '14 at 8:41

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?

• How did you do the brute force search? The search space is too large even with some optimizations. – vapor Feb 23 '18 at 16:24
• @happyfish: I'll see if I can find my old search script (I don't have it on this computer), but IIRC the basic idea was to keep track of all the differences between pairs of subset sums (i.e. ages that cannot be added to the current partial solution). Also, if you're looking for an $n$-person solution, you can backtrack as soon as the current partial solution size plus the number of remaining possible ages becomes less than $n$, which should save a bit of time (although I honestly can't remember if I made use of that optimization or not). – Ilmari Karonen Feb 23 '18 at 20:08

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.

• 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
• @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.

• 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
• 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

A group of $9$ is sufficient to get matching age groups, using a small extension on estimating the range of possible sums.

As observed the number of non-empty subsets will be $2^9-1=511$ and as before we can assume that all ages are different, since otherwise we can just use two people with the same age to achieve our goal.

Now consider the youngest person, with an age of $y$ - this is the lower limit of possible age sums. The upper limit is then at most $y+\sum_{53}^{60}i = y+452$. There are thus $453$ or fewer different age sums available for different groups and thus the pigeonhole principle applies, where two groups must have the same age sum.

Clearly we can extend the age limit also: $9$ people of up to age $67$ will still produce groups with a common age sum from this still fairly simple process.

At the cost of sacrificing a few less-useful subsets, we can reduce the totals range further also. The full set 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 example for $10$ people, considering the $1013$ groups defined under this process we can impose an age limit of $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.

The corresponding age limits for some smaller groups are:

$$\begin{array}{c|c|c} \text{# people} & \text{# useful subsets} & \text{age limit}\\ \hline 10 & 1013 & 130 \\ 9 & 502 & 75\\ 8 & 247 & 44\\ 7 & 120 & 26\\ 6 & 57 & 16\\ 5 & 26 & 10 \end{array}$$

But note that these age limits are likely underestimates. For example, in the last case, the logic to achieve this has assumed we have ages of $\{10,9,8,7\}$ which immediately produce two groups of equal age sum ($10+7=9+8$). In fact leaving only one "young end" age can produce huge gaps in the possible age sums (fewer holes for our pigeons). So it is entirely likely that the age limits are somewhat higher and I am not surprised by the claim that a group of $8$ could potentially have an age limit of $60$ and still necessarily have same-age-total groups.

In your solution, you have mentioned that the maximum sum is 60. But notice that if there were two people of the same age then we are done as we can easily choose the two persons as a different group. So it should be distinct, i.e., max sum= $\displaystyle\sum_{i=0}^9 (51+i)=\dfrac{10}{2}(51+60)=555$. But here comes the surprise, the minimum sum = $\displaystyle\sum_{i=0}^9 (1+i)=\dfrac{10}{2}(1+10)=55$, and the total number of sums using inclusion and exclusion principle we get, $555-55+1=501$. Here see that $2^9-1=511$, hence @Ilmari Karonen did not encounter any problem with 9 number set with his brute force algorithm.

But we are not done here, notice that $2^8-1=255<501$. It simply implies that we can always find a subset such that no 2 groups of people will have the same age. Here we have reduced the number of possible sums, which is very important as no we get the reduced possibilities ignoring all that impossible cases. You can try to prove that 8- number set is not possible to obtain.